알고리즘/Baekjoon
[PS] GCD(n, k) = 1 / C++ (백준 11689번)
dh_0e
2025. 3. 14. 17:11

1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제
깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다.

시행 착오
에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다.
풀이 과정
사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.
나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다.
※ N=99처럼 sqrt(N)보다 N의 약수(11)가 더 큰 경우가 있으므로 이 경우엔 N이 1까지 나눠지지 못했기 때문에 마지막에 예외처리를 해주어야 함
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
pair<ll, ll> pa = make_pair(0, 0);
ll n, dap = 1;
scanf("%lld", &n);
int sqrt_n = sqrt(n);
for (ll i = 2; i <= sqrt_n; i++) {
if (n % i == 0) {
int c = 0;
while (n % i == 0) {
n /= i;
c++;
}
dap *= pow(i, c - 1) * (i - 1);
}
}
if (n > 1) {
dap *= n - 1;
}
printf("%lld\n", dap);
return 0;
}