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

문제 링크

www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1

 

풀이

오일러 파이함수 $\phi(n)$를 구현하는 문제입니다. 어떤 수 $n$의 소인수 개수를 $m$개라 합시다.

$$\begin{eqnarray}\phi(n) &=& n\prod_{p|n}(1-\dfrac{1}{p}) \\ &=& n(1-\dfrac{1}{p_1})(1-\dfrac{1}{p_2})...(1-\dfrac{1}{p_{m}})\end{eqnarray}$$

식의 앞에서부터 차례대로 전개하는 방식으로 구현하시면 됩니다.

 

정답 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

    ll n;
    cin >> n;
    ll ans = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans -= ans / i;
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) {
        ans -= ans / n;
    }
    cout << ans;
}