백준 23832번: 서로소 그래프 (C++)

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

23832번: 서로소 그래프

---

Solved By: Euler Phi Function

 

노드 N에서 나와야 하는 간선의 개수는 N이하의 양의 정수 중 N과 서로소의 개수다. 즉, EulerPhi(N)과 같다.

이를 이용하여 2 ~ N까지의 EulerPhi값들의 합을 구해주면 된다.

 

EulerPhi를 연산하는 과정에서 overflow가 날 수도 있으므로 long long으로 선언하고 풀어준다.

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

int N;

ll eulerPhi(int n){
    ll ret = n;
    int temp = n;
    vector<int> factors;
    for(int i = 2; i <= sqrt(n); i++){
        if(temp % i == 0){
            factors.push_back(i);
            while(temp % i == 0) temp /= i;
        }
    }
    
    if(temp > 1){
        factors.push_back(temp);
    }
    
    for(auto v : factors){
        ret = ret * (v - 1) / v;
    }
    
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    ll res = 0;
    for(int i = 2; i <= N; i++){
        res += eulerPhi(i);
    }
    cout << res;
    return 0;
}