RUPC (Ritsumeikan University Programming Contest) 2011 Problem F Farey Sequence

問題

集合の列Fiは、
Fi={i以下の分母を持つ既約分数}からなる集合の列である。

F1={0/1,1/1}
F2={0/1,1/2,1/1}
F3={0/1,3/1,1/2,2/3,1/1}
……

となる。
Fのi番目の集合Fiの要素の数を求めよ。

制約条件

i≦10^6

方針

要素の数はΣ(分母と互いに素である自然数の数)+1である。

分母とお互いに素である自然数の数はオイラー関数そのものなので、
これの累積和を取っていけばいい。

ソースコード

const int N = 1000001;
int p[N], f[N];
ll ans[N];
void precalc() {
  rep(i,N) p[i] = 1, f[i] = i;
  for (int i = 2; i < N; ++i) {
    if (p[i]) {
      f[i] -= f[i] / i;
      for (int j = i+i; j < N; j+=i)
        p[j] = 0, f[j] -= f[j] / i;
    }
  }
	ans[1]=2;
	for(int i=2;i<N;i++)ans[i]=ans[i-1]+f[i];
}

int main()
{
	precalc();
	int t; cin>>t;
	
	rep(T,t){
		int n; cin>>n;
		cout<<ans[n]<<endl;
	}
	return 0;
}