POJ 2478 - Farey Sequence

http://poj.org/problem?id=2478

概要

ファレイ数列とは，ある n について，既約分数 a/b (0 < a < b <= n) からなる数列である．

n 番目のファレイ数列の項数を答える．

制約

• 2 <= n <= 10^6

解法

n 番目のファレイ数列の項数を F[n] とすると，F[n] = F[n-1] + (n の約数の数) で計算できる．

n の約数の数はオイラーのφ関数で計算できる．

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int primes[100000];
 5 int prime_size;
 6 
 7 int phi(int n)
 8 {
 9   int ans = n;
10   for (int i = 0; primes[i]*primes[i] <= n; i++) {
11     if (n % primes[i] == 0) {
12       ans -= ans / primes[i];
13       while (n % primes[i] == 0) {
14         n /= primes[i];
15       }
16     }
17   }
18   if (n > 1) {
19     ans -= ans / n;
20   }
21   return ans;
22 }
23 
24 int main()
25 {
26   static const int N = 1000000;
27   static bool sieve[N+1];
28   for (int i = 2; i <= N; i++) {
29     if (!sieve[i]) {
30       primes[prime_size++] = i;
31       for (int j = i+i; j <= N; j += i) {
32         sieve[j] = true;
33       }
34     }
35   }
36   static long long f[N+1];
37   for (int i = 2; i <= N; i++) {
38     f[i] = f[i-1] + phi(i);
39   }
40 
41   int n;
42   while (cin >> n && n != 0) {
43     cout << f[n] << endl;
44   }
45   return 0;
46 }