cf #538 div2 C - Trailing Loves (소인수분해, 수학)

https://codeforces.com/contest/1114/problem/C

n! 에 어떤 소수가 몇개 들어있는지 로그시간에 파악하는 법 확인.

오버플로우를 피하기 위한 조건문 확인.

 

<문제설명>

최대 1e18의 n과 최대 1e12의 b가 주어진다.

n!을 b진법으로 표현했을 때 trailing zero의 수를 세라.

(ex. 9800은 10진법으로 trailing zero가 두개 있다.)

 

<풀이>

n!을 b로 몇번 나눌 수 있는지 구하면 된다.

 

b를 소인수분해하여 p ^ x꼴의 인수들에 대해서, n!에 그 하나하나의 인수가 나오는 횟수들의 최소를 구하면 된다.

 

n!에 어떤 소수 x가 몇 개 들어있는지 반환하는 함수 f를 이용해서 풀 수 있다.

ll f(ll x) {
	ll ret = 0;
	ll t = x;
	x = 1;
	while (x <= n/t) {
		x = x * t;
		ret += n / x;
	}
	return ret;
}

 

오버플로우때문에 while 조건문으로 x*t<=n을 사용하지 못한다. 변형하여 x<=n/t를 사용하면 오버플로우를 피할 수 있다.

 

 

<코드>

ll n, b, mn=2e18;
vector<P> coprime;

ll f(ll x) {
	ll ret = 0;
	ll t = x;
	x = 1;
	while (x <= n/t) {
		x = x * t;
		ret += n / x;
	}
	return ret;
}

int main() {
	FAST; cin >> n >> b;
	ll t = b;
	for (ll i = 2; i * i <= t; i++) {
		if (t % i == 0) {
			ll cnt = 0;
			while (t % i == 0) {
				t /= i;
				cnt++;
			}
			coprime.push_back({ i,cnt });
		}
	}
	if (t != 1) coprime.push_back({ t,1 });

	for (P p : coprime) {
		ll x, y; tie(x, y) = p;
		mn = min(mn, f(x) / y);
	}
	cout << (mn==2e18?0:mn) << '\n';
}