BackJoon_소수 찾기

문제

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

입력

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

출력

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

예제

• Example 1:

Input:
5 2

Output:
3

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int main()
{
	int n, a, m, count;

	scanf("%d %d", &n, &a);
	m = n / a;
	count = m;
	while (m >= a)
	{
		m /= a;
		count += m;
	}
	printf("%d", count);
	return 0;

}

풀이

• 팩토리얼을 직접 구하면 시간 초과가 뜨기 때문에 정수론을 이용해서 푼다.

결과

Runtime 0 ms / Memory 2020 KB

---

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