BOJ 7806 - GCD!

[ 분류 - GCD ]

재밌는 문제다.

이 문제는 팩토리얼과의 GCD를 구하는 문제다.

GCD에 요소가 될 수 있는 후보를 먼저 생각해보자. n!은 우선 냅두고.. k를 생각하자. n!은 너무 값이 클 수 있기 때문이다.

그렇다면 GCD 후보는 k의 약수로 요약할 수 있다. 또한 k를 소인수 분해하여 정리하면 아래와 같이 표현할 수 있다.

따라서 후보는 1부터 n을 곱했을 때, 그 값에서 소수 p1부터 px까지로 포함된 최대의 수로 나타낼 수 있다.

즉,  로 표현할 수 있다.

따라서 를 아래 수식처럼 표현할 수 있다.

접근법을 알았으니, 이제 n!에 대해 gx 값을 구하는 방법을 알아보자.

간단하게 나누기로 특정 소수의 px의 승수를 쉽게 알아낼 수 있다.

만약 px=2이라면 아래처럼 표현할 수 있다.

- 코드

#include <cstdio>
#include <cmath>
#include <vector>
int min_v(int a, int b) { return a < b ? a : b; }
struct _d { int d, c; };
int main() {
	int n, k, l, i, tc,res;
	long long cur;

	while (~scanf("%d%d", &n, &k)) {
		std::vector<_d> factors, ans;
		l = sqrt(k);
		for (i = 2; i <= l; i++)
			if (!(k%i)) {
				_d t{ i,0 };
				while (!(k%i)) {
					k /= i;
					t.c++;
				}
				factors.push_back(t);
			}
		if (k != 1) factors.push_back(_d{ k,1 });
		for (_d& t : factors) {
			cur = t.d;
			tc = 0;
			while (cur <= n) {
				tc += n / cur;
				cur *= t.d;
			}
			ans.push_back(_d{ t.d, min_v(t.c, tc) });
		}
		res = 1;
		for (_d& t : ans)
			res *= pow(t.d, t.c);
		printf("%d\n", res);
	}
	return 0;
}