[백준(BOJ)] GCD(n, k) = 1(11689번)_C++

오일러의 토션트 함수에 대해 공부해보자.

대충 간략하게 설명해보자면 다음과 같다.

 

f(n) 은 1~n까지 n과의 최대공약수가 1인 수들의 개수라고 말할 수 있다.

n = a*b 를 만족하는 서로소 a, b에 대하여 f(n) = f(a) * f(b)

f(p^k) = p^(k - 1) * (p - 1)

 

위의 내용을 가지고 이 문제를 쉽게(?) 해결할 수 있다.

계속 곱셈만 수행하기 때문에 정답인 answer은 곱셈의 항등원인 1로 초기화했다.

 

i = 2부터 검사를 시작하는데(1은 어차피 최대공약수가 1) n이 i로 나누어 떨어지면 n = i * x라 할 수 있다.

i와 x가 서로소일 수도 있다. 그러나 그 안에 if문에서 i를 모조리 없애줄 것이다.

우선 f(i) = i ^(1 - 1) * (i - 1)이므로 우선 answer에 i - 1을 곱해준다.

이제 n에서 i를 모조리 없애줄 것이다. n이 i로 나누어떨어지지 않을 때까지 i로 나누면서 그 횟수만큼 answer에 i를 곱한다.

이제 n은 i를 포함해 i의 배수를 인수로 갖지 않는다. 즉, n = i^(i횟수) * x 이고 i^(i횟수)와 x는 이제 서로소이다.

그러면 answer에는 i^(i횟수) * (i - 1)이 곱해진 상태이다. 실제로는 i^(i횟수 - 1) * (i - 1)이 곱해져야하므로 while문을 나온 뒤에 answer /= i 를 해준 모습을 볼 수 있다.

 

이제 어느 정도 이해가 되지 않는가?

그런데 for문에서 i <= n / i가 의문일 수도 있다.

우선 for문의 조건을 i * i <= n 으로 해도 되는 이유부터 설명하겠다.

 

if (n % i == 0) 을 검사할 때 i가 n의 제곱근보다 커지면 검사하는 의미가 있는지 잘 생각해보기를 바란다.

i가 n의 제곱근보다 커지면 어차피 n은 i로 나누어떨어질 수가 없다. 아니 나누어떨어질 수는 있는데 이미 처리됐다.

예를 들어 n = 8 이라 해보자. i=2부터하면 n = i * 4이다. 그럼 4일 때도 처리가 된 것이다.

이해가 되었길 바라며...

 

그래서 i * i <= n을 조건해로 해도되는데 이 때 i는 int형이다. i * i를 연산하다보면 분명 int형 범위를 넘길 수 있다.

그러므로 i <= n / i를 한 것이다.

 

 

---

정답

#include <iostream>

using namespace std;

long long n;
long long answer = 1;

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    //input
    cin >> n;

    //Euler's totient function
    for(int i = 2; i <= n / i; i++){
        if (n % i == 0){
            answer *= i - 1;

            while (n % i == 0){
                answer *= i;
                n /= i;
            }
            answer /= i;
        }
    }

    if (n != 1)
        answer = answer * (n - 1);

    //output
    cout << answer;
}