[백준 11689] GCD(n, k) = 1 [C]

백준 - 11689

---

풀이

Euclidean algorithm을 사용해 풀이할 수 있지만, 최대 10^12의 수들에 대해 계산을 해야하므로 시간제한에 걸린다.

Euler product formula을 사용해 쉽게 풀이할 수 있다.

위키백과 - 오일러 피 함수

나누어 떨어지는 소인수(p)를 찾아 Euler product formula에 적용시키면 된다.

p-1 / p (= 1- 1/p)를 n에 곱해주어야 한다. p로 먼저 나눈 후 p-1을 곱해주자.

for (long long p = 2; p*p <= n; pf++){
    if (n % p == 0) euler = euler/p *(p - 1);

그런 다음 계속해서 소인수를 찾을지 말지 여부를 결정해주기 위해 n이 p로 나누어 떨어지지 않을 때까지, n에 대하여 Euler product formula을 적용시키면 된다.

    while (n % p == 0) n = n/p;

 

 

다음과 같은 예외가 있다.

• n이 소수일 때 
• n이 지수가 1인 소인수를 가질 때

Euler product formula을 1회 적용해 두 조건에 대한 euler를 얻을 수 있다.

---

소스코드

#include <stdio.h>
int main(){
    long long n;
    scanf("%lld", &n);
    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 == 1 ? euler : euler/n *(n - 1));
}

---

출처 및 참고자료

11689번: GCD(n, k) = 1

오일러 피 함수 - 위키백과, 우리 모두의 백과사전