728x90
풀이
"백준 11689, GCD(n, k) = 1"를 이용해 풀이했다.
시간초과는 발생하지 않으니 그냥 0을 입력받을 때까지 반복하면된다.
소스코드
#include <stdio.h>
int main(){
long long n;
while (1){
scanf("%lld", &n);
if (!n) break;
long long euler = n;
for (long long p = 2; p*p <= n; p++){
if (n % p == 0) euler = euler/p *(p - 1);
while (n % p == 0) n = n/p;
}
printf("%lld\n", n == 1 ? euler : euler/n *(n - 1));
}
}
출처 및 참고자료
4355번: 서로소
입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 n ≤ 1,000,000,000으로 이루어져 있다. 입력의 마지막 줄에는 0이 주어진다.
www.acmicpc.net
[백준 11689] GCD(n, k) = 1 [C]
풀이 Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다. Euler product formula을 사용해 쉽게 풀이할 수 있다. 나누어 떨어지는 소인수(pf)를..
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 2178] 미로 탐색 [C] (0) | 2021.08.13 |
---|---|
[백준 14860] GCD 곱 [C] (0) | 2021.08.11 |
[백준 11689] GCD(n, k) = 1 [C] (0) | 2021.08.11 |
[백준 17626] Four Squares [C] (0) | 2021.08.11 |
[백준 15657] N과 M (8) [C] (0) | 2021.08.10 |