POJ 2478 Farey Sequence

Description

The Farey Sequence Fn for any integer n with n >= 2 is the set of irreducible rational numbers a/b with 0 < a < b <= n and gcd(a,b) = 1 arranged in increasing order. The first few are 
F2 = {1/2} 
F3 = {1/3, 1/2, 2/3} 
F4 = {1/4, 1/3, 1/2, 2/3, 3/4} 
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5} 

You task is to calculate the number of terms in the Farey sequence Fn.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (2 <= n <= 10  ⁶). There are no blank lines between cases. A line with a single 0 terminates the input.

Output

For each test case, you should output one line, which contains N(n) ---- the number of terms in the Farey sequence Fn. 

Sample Input

2 3 4 5 0

Sample Output

1 3 5

9

线性筛求欧拉函数。

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int mod = 998244353;
const int N = 1e6 + 10;
int n;
LL sum[N];
int phi[N], f[N], p[N], t;

void init()
{
  t = 0;  sum[1] = phi[1] = f[1] = 1;
  rep(i, 2, N - 1)
  {
    if (!f[i]) p[t++] = i, phi[i] = i - 1;
    for (int j = 0,k; j < t&&p[j] * i < N; j++)
    {
      k = p[j] * i; f[k] = 1;
      phi[k] = phi[i] * (p[j] - 1);
      if (i % p[j] == 0) { phi[k] = phi[i] * p[j]; break; }
    }
    sum[i] = sum[i - 1] + phi[i];
  }
}

int main()
{
  init();
  while (scanf("%d", &n), n) printf("%lld\n", sum[n] - 1);
  return 0;
}