[백준]11689 GCD(n,k) - 오일러 파이 함수

문제

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다.

출력

GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.

 

자연수 N이 있을때, N보다 같거나 작은 수 중에서 N과 소인수인 수의 개수를 구하는 문제입니다.

 

오일러 파이함수를 사용해 해결할 수 있습니다.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {

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