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를 출력한다.
풀이)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
// 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;
}
|
cs |
출처 : https://www.acmicpc.net/problem/15996
'Develop > 백준 (Cpp)' 카테고리의 다른 글
[백준] 2436번 : 공약수 (C++) (0) | 2024.01.14 |
---|---|
[백준] 6219번 : 소수의 자격 (C++) (0) | 2024.01.14 |
[백준] 2725번 : 보이는 점의 개수 (C++) (0) | 2024.01.14 |
[백준] 2004번 : 조합 0의 개수 (C++) (0) | 2024.01.14 |
[백준] 1676번 : 팩토리얼 0의 개수 (C++) (0) | 2024.01.13 |