[BOJ] 11525 - Farey Sequence

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

BOJ - Farey Sequence

문제 유형: 수학, 정수론, 오일러 피 함수, 누적 합

문제 난이도: Gold I

시간 제한: 1초

메모리 제한: 256MB

 

문제

Given a positive integer, N, the sequence of all fractions a / b with (0 < a < b), (1 < b < N) and a and b relatively prime, listed in increasing order, is called the Farey Sequence of order N.

For example, the Farey Sequence of order 6 is:

0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1

For this problem, you will write a program to compute the length of the Farey sequence of order N (input). 

 

양의 정수 n이 주어집니다.  (0 < a <= b), (1 < b <= N)을 만족하는 기약분수 a/b의 개수를 구하시오.

 

입력

The first line of input contains a single integer P, (1 ≤ P ≤ 10000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, K, followed by the order N, N (2 ≤ N ≤ 10000), of the Farey Sequence whose length is to be found.

 

첫째 줄에 정수 P가 주어집니다.

이후 P개의줄에 K와 N이 주어집니다.

 

출력

K번째 쿼리에 대해 N인경우의 답을 구해서 출력하시오.

 

풀이

각 분모에 대해서, 자신보다 작은 수들 중 자신과 서로소인 분자들의 개수를 구해야 하고, 이는 오일러 피 함수로 구할 수 있다.

각 쿼리의 응답은 결국 

이다.

이는 누적합으로 미리 구해놓으면 편하게 출력 가능하다.

오일러 피 함수의 구현은 아래 코드의 phi 함수를 참조.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int phi(int n) {
    int res = n;
    for(int i = 2; i * i <= n; i++) {
        if(n % i == 0) {
            while(n % i == 0) {
                n /= i;
            }
            res -= res/i;
        }
    }
    if(n > 1) {
        res -= res / n;
    }
    return res;
}

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

    int p;
    cin >> p;
    vector<int> ans(10001);
    ans[1] = 2;
    for(int i = 2; i <= 10000; i++) {
        ans[i] = ans[i-1] + phi(i);
    }

    while(p--) {
        int k, n;
        cin >> k >> n;
        cout << k << " " << ans[n] << "\n";
    }
}