n, k가 입력으로 주어지고 GCD(n!,k)를 구하는 문제입니다.
GCD(n!, k)을 구하려면 우선 n! 을 구해야 하는데
n이 최대 10억이므로 n! 을 구하면 시간 초과가 됩니다…
다른 방법으로 접근해야 합니다.
최대 공약수를 다시 한번 생각해보면 GCD(a, b) = c 일 때 a % c = 0, b % c = 0입니다.
n! 은 1~n까지 숫자들의 곱이므로 1~n의 숫자들 중 아무 숫자나 하나씩 랜덤으로 뽑은 뒤 곱해도 n!의 약수입니다.
이를 이용하여 k를 소인수 분해를 하여 쪼갠 뒤 1~n 숫자들과 비교를 하여 약수를 구할 수 있습니다.
k를 소인수 분해했을 때 \(2^a \times 3^b \times 7^c\) 라고 했을 때
n!를 \(2^x \times 3^y \times 5^w \times 7^z \times ···\)의 형태로 생각하여 k와 겹치는 부분만 봐주면 됩니다.
최대공약수를 찾는 것이므로 \(2^{min(a,x)}\times 3^{min(b,y)} \times 7^{min(c,z)}\) 가 최대공약수가 됩니다.
n! 을 소인수 분해를 하여 저 형태로 만드는 것은 너무 오래 걸리니
1~n에서 2를 1번 곱하는 수의 개수, 2번 곱하는 수의 개수, 3번 곱하는 수의 개수···를 구하여 더하면 n!의 2^x를 알 수 있습니다i.
k를 소인수 분해하며 저 과정을 하게 되면 최대공약수를 구할 수 있습니다.
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
using namespace std;
ll pw(ll a, ll b) {
ll ret = 1;
while (b) {
if (b & 1) ret *= a;
a *= a, b >>= 1;
}
return ret;
}
int main() {
FIO;
ll n, k;
while (!cin.eof() && cin >> n >> k) {
if (!n) n++;
ll ans = 1, temp = k;
for (ll i = 2; i * i <= temp; i++) {
if (k < i) break;
ll a = 0, b = 0;
while (!(k % i)) k /= i, a++;
for (ll j = i; j <= n; j *= i) b += n / j;
ans *= pw(i, min(a, b));
}
cout << ans * (k <= n ? k : 1) << '\n';
}
return 0;
}