AOJ 2286 - Farey Sequence

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2286

解法

POJ 2478 - Farey Sequence と同じ． ただし，こちらの Farey Sequence は 0/1 と 1/1 も含んでいるので F[1] = 2 から始める．

 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   f[1] = 2;
38   for (int i = 2; i <= N; i++) {
39     f[i] = f[i-1] + phi(i);
40   }
41 
42   int T;
43   cin >> T;
44   while (T-- > 0) {
45     int n;
46     cin >> n;
47     cout << f[n] << endl;
48   }
49   return 0;
50 }