AOJ 2286 : Farey Sequence

問題リンク:Farey Sequence | Aizu Online Judge

問題概要：
略

解法：
オイラーのΦ関数を使う
i == 0 のとき、F_0 = 2
その他のとき、F_i = F_i-1 + (iと互いに素なものの数) となる
iと互いに素なものの数はオイラーのΦ関数で求める
前処理でFを作っておいて、あとは入力をとって出力するだけにしておく

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define MAX_N 1000100

using namespace std;

typedef unsigned long long ll;

ll euler[MAX_N];
ll answer[MAX_N];

void euler_phi2(){
  for(ll i=0;i<MAX_N;i++)euler[i] = i;
  for(ll i=2;i<MAX_N;i++){
    if(euler[i] == i){
      for(ll j=i;j<MAX_N;j+=i)euler[j]=euler[j]/i*(i-1);
    }
  }
}

int main(){
  euler_phi2();
  answer[1] = 2;
  REP(i,2,MAX_N)answer[i] = answer[i-1] + euler[i];
  int t,n;
  scanf("%d",&t);
  rep(_,t){
    scanf("%d",&n);
    printf("%lld\n",answer[n]);
  }
  return 0;
}