목록gcd(n. k) = 1 (1)

dh_0e

[PS] GCD(n, k) = 1 / C++ (백준 11689번)

1~$10^{12}$ 범위인 N과 서로수인 수의 개수를 구하는 문제 깡으로 하면 무조건 시간 초과이므로 오일러 피 함수의 성질을 이용해서 풀 수 있다.  시행 착오에라토스테네스의 체로 소수를 모두 구별하여 N을 소인수분해 한 뒤, 오일러 피 함수의 성질을 이용하여 답을 도출하는 식으로 구상했지만, $10^{12}$ 이하의 가장 큰 소수가 999999999989이므로 당연히 메모리 초과가 나왔다. 풀이 과정사실 2부터 시작해서 N의 값을 나눌 수 있을 때까지 나누면 소수를 따로 구할 필요없이 소수로만 나눌 수 있다.나눌 때마다 오일러 피 함수의 성질을 이용하여 변수를 지정해 곱해놓으면 답을 구할 수 있다. ※ N=99처럼 sqrt(N)보다 N의 약수(11)가 더 큰 경우가 있으므로 이 경우엔 N이 1까지 ..
알고리즘/Baekjoon 2025. 3. 14. 17:11
이전 Prev 1 Next 다음