백준 11689 GCD(n, k) = 1 C++

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

11689번: GCD(n, k) = 1

오일러 파이 함수를 구하는 문제입니다.

오일러 파이 함수는 phi(n) = n * (1-1/p1) * ... * (1-1/pk) 입니다.

(p1, p2, ..., pk : n의 소인수)

 

이를 이용해 n에 대한 소인수만 먼저 구한 뒤 공식을 그대로 적용하면 됩니다.

 

코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long n;
vector<long long> factors;
// 오일러 파이 함수 공식 그냥 쓰기
// 소인수만 찾으면 됨

void init()
{
    cin >> n;
}

void calc_factors()
{
    long long p;
    long long num = n;
    // root(n) <= 10^6
    for(p = 2; p * p <= num; p++) {
        if(num % p == 0) {
            factors.push_back(p);
        }
        
        while(num % p == 0) {
            num /= p;
        }
    }
    
    // root(n)보다 큰 소수 남은 거
    // 또는 n이 prime인 경우
    if(num > 1)
        factors.push_back(num);
}

void euler()
{
    // n = 1 경우
    if(n == 1) {
        cout << 1;
        return;
    }
    
    // n 소수인 경우
    if(factors[0] == n) {
        cout << n - 1;
        return;
    }
    
    // 나머지 경우
    long long ans = n;
    for(auto p : factors) {
        ans /= p;
        ans *= (p - 1);
    }
    
    cout << ans;
}

int main()
{
    init();
    calc_factors();
    euler();
}