Algoogle

Algorithm for Programming Contest

AOJ 2286 Farey Sequence

Category: AOJ Tag: math

Farey Sequence

問題概要


n以下の分母を持つ0以上1以下のすべての既約分数の数を求めよ

解法


Farey数列と呼ばれるもので,オイラーの 関数から求めることができる.

これを前計算でやればよい.

コード


(2286.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

const int N = 1000001;
long long farey[N];
bool p[N];
int n;
vector<int> fc[N];

long long solve() {
    return farey[n];
}

void prepare() {
    p[0] = p[1] = 1;
    rep(i,N) if(!p[i]) {
        fc[i].push_back(i);
        for (int j = i+i; j < N; j+=i) {
            p[j] = 1;
            fc[j].push_back(i);
        }
    }

    farey[0] = 1;
    repi(i,1,N) {
        long long num = 1, den = 1;
        for(auto &e: fc[i]) { den *= e; num *= e-1; }
        farey[i] = farey[i-1]+i/den*num;
    }
}

void input() {
    cin >> n;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cout << fixed << setprecision(12);
    int t; cin >> t;
    prepare();
    while(t--) {
        input();
        cout << solve() << endl;
    }
    return 0;
}

Comments