백준 11525번: Farey Sequence Length (C++)

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

11525번: Farey Sequence Length

---

Solved By: Euler Phi Function

 

이번 문제를 풀면서 페리 수열에 대해 공부해봤습니다.

(https://ko.wikipedia.org/wiki/%ED%8E%98%EB%A6%AC_%EC%88%98%EC%97%B4)

공부를 하다 보면 수열의 길이를 증명하는 과정이 나옵니다. 증명을 통해 나온 공식을 사용하여 이번 문제를 풀 수 있습니다.

공식에는 오일러 파이 함수가 사용되니 이를 알고 있어야 합니다.

출처: 위키백과

그리고, 여러 케이스를 한 번에 돌리면서 같은 Euler Phi 값이 여러 번 호출되어 시간 초과를 유발할 수 있기 때문에 Memoization으로 이를 기억하여 다시 사용합시다.

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 10001
using namespace std;

int N;
int cache[MAX];

int eulerPhi(int n){
    int 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 cache[n] = ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for(int t = 1; t <= N; t++){
        int tt, n; cin >> tt >> n;
        int result = 0;
        for(int i = 1; i <= n; i++){
            if(cache[i]) result += cache[i];
            else result += eulerPhi(i);
        }
        result++;
        cout << tt << ' ' << result << '\n';
    }
    return 0;
}