문제
https://www.acmicpc.net/problem/7806
문제해설
문제 자체는 간단하다.
n과 k가 주어지는데 n!과 k의 최대공약수를 구하면 된다.
문제풀이
엄청 어려운 문제다.. 결국 혼자서 풀지 못했고 다른 사람의 풀이를 참고했다.
참고하면서도 어떻게 이런 생각을 했는지 참 신기했다.
예를 들어 n이 4 k가 60이라면
문제에서 주어진 방법대로 하면 4!인 24과 60의 최대공약수인 12가 정답이다.
하지만 n이 최대 10억까지 들어오는데 펙토리얼만 구해도 시간초과다.
새로운 방법은 k의 소수들만 생각하는 것이다.
왜냐하면 GCD(a, b)=c 일 때, a는 c로 나누어 떨어지고 b도 c로 나누어 떨어지기 때문이다.
60을 소인수분해하면 60 = 2^2 * 3 * 5 가 나온다.
그럼 이제 4!에서 2와 3과 5만 판단하면 된다.
4! = 2^3 * 3 이고 60과의 공통된 소인수는 2와 3이다.
공통된 지수에서 작은 지수를 골라 곱해주면 2^2 * 3 = 12 최대공약수가 나온다.
전체코드
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
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int n, k;
while (!cin.eof() && cin >> n >> k) {
ll res = 1;
// 에라토스테네스의 체를 생각해서 루트까지만 돈다
for (int i = 2; i <= sqrt(k); i++) {
int primeK = 0; // k에 대한 i 지수의 갯수 예를들어 i=3 일 때 primeK=4 이라면 3^4가 약수
while (k % i == 0) {
k /= i;
primeK++;
}
int primeN = 0; // k와 마찬가지로 n에 대한
if (primeK > 0) {
for (int j = i; j <= n; j *= i) // 이 부분은 다른 코드를 그대로 참고했는데 참신했다
primeN += n / j;
}
res *= pow(i, min(primeK, primeN));
if (k < i)
break;
}
// k가 n보다 클 때 n!을 소인수분해 한다면 k가 무조건 존재한다
if (k > 1 && k < n)
res *= k;
cout << res << "\n";
}
return 0;
}