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

 

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

 

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

11689번: GCD(n, k) = 1

---

해결전략

 

수학

오일러 파이함수 

---

 

정답코드

 

#include <iostream>.
using namespace std;

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

    long long n;
    cin >> n;

    long long answer = n; // 오일러 피를 계산할 변수를 선언하고, 초기값으로 n을 할당.

    for (long long i = 2; i * i <= n; i++) // 2부터 n의 제곱근까지 순회하며
    {
        if (n % i == 0)  // 만약 n이 i로 나누어 떨어지면, 즉 i가 n의 약수라면
        {
            answer -= answer / i;  // answer에서 answer/i를 뺌. 이는 오일러 피 계산 공식의 일부임.

            while (n % i == 0) {  // n이 i로 나누어 떨어지는 동안 계속 나눔. 이는 n을 소인수분해하는 과정.
                n /= i;
            }
        }
    }

    // 위의 for문을 거치고 남은 n이 1보다 크다면, 즉 n이 소수라면
    if (n > 1) {
        answer -= answer / n; // answer에서 answer/n을 빼줍니다.
    }

    cout << answer; // 계산된 오일러 피 값을 출력
}

 

---