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

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다!

https://rudalsd.tistory.com/59?category=1064608 

[ 알고리즘 ] 오일러 피 함수(Euler's phi function)

 

위의 공식을 이용하여 ans에 n을 대입한 후 n에 대하여 어떠한 수 i로 나누어지면 ans = ans - ans / i를 통해서 답을 구할 수 있습니다.

 

이때 i * i <= n까지 구하는 이유는 n의 제곱근은 i보다 작거나 같기때문입니다.

 

하지만 마지막에 n이 1이 아니라면 남은 n은 소수이므로 n이 1이 아닐 때 마지막으로 ans = ans - ans / n을 해주면 답을 구할 수 있습니다.

 

[ 소스 코드 ]

#include<iostream>
 
#define ll long long
 
using namespace std;
 
ll n;
ll ans;
 
int main()
{
    cin >> n;
    ans = n;
 
    for (ll i = 2; i * i <= n; i++) {
        int cnt = 0;
        bool flag = false;
        while (n % i == 0) {        //소인수분해
            n /= i;
            flag = true;
        }
 
        if (flag) {        //오일러 피
            ans = ans - ans / i;
        }
    }
 
    if (n != 1) {        //남은 n이 소수라면
        ans = ans - ans / n;
    }
 
    cout << ans;
}