[백준] 15996번 : 팩토리얼 나누기 (C++)

15996번 : 팩토리얼 나누기

---

문제)

음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1)

 

 

 

 

입력 :

첫째 줄에 정수 N과 A가 사이에 공백을 두고 주어진다. (0 ≤ N < 2^31, 2 ≤ A ≤ 11, A는 소수)

 

 

 

 

출력 :

첫째 줄에 최대의 음이 아닌 정수 k를 출력한다.

 

 

 

 

 

 

풀이)

// 15996. 팩토리얼 나누기
#include <iostream>
 
using namespace std;
 
int prime_cnt(long long _n, long long _a)
{
    // n!에 있는 소수 a의 개수 찾기
    long long cnt = 0;
    for(long long i = _a ; i <= _n; i *= _a)
    {
        cnt += _n / i;
    }
 
    return cnt;
}
 
 
int main()
{
    long long n, a;
    cin >> n >> a;
 
    cout << prime_cnt(n, a);
 
    return 0;
}
 

 

---

출처 : https://www.acmicpc.net/problem/15996 

15996번: 팩토리얼 나누기