RUPC F, AOJ-2286: Farey Sequence

問題概要

N(<10^6)が与えられる。0以上1以下の既約な有理数で、分母がN以下であるようなものが何通りあるか求める問題。テストケース10^6くらい。

考えたこと

• 即数列検索。
• ヒット。何かΦ関数が見える。
• 言われてみればそれは自明。漸化式a[1]=2, a[i] = a[i-1] + card({x in [1..i] | xとiは互いに素}) = a[i-1] + Φ(i)。
• 後は書くだけ。無事通った。

本番で通ったコード

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
const int MAX_N = (int)(1e6);

int64 phi[MAX_N + 1];
int64 fs[MAX_N + 1];
int64 ans[MAX_N + 1];
int64 accum[MAX_N + 2];

void euler_phi(){
	for(int i=0; i<=MAX_N; i++){
		fs[i] = true;
		phi[i] = i;
	}

	for(int i=2; i<=MAX_N; i++){
		if(fs[i]){
			phi[i] -= phi[i] / i;
			for(int j=2*i; j<=MAX_N; j+=i){
				fs[j] = false;
				phi[j] -= phi[j] / i;
			}
		}
	}
}

void pre_solve(){
	euler_phi();

	for(int i=1; i<=MAX_N; i++){
		accum[i] = accum[i-1] + phi[i];
	}

	for(int i=1; i<=MAX_N; i++){
		ans[i] = 1 + accum[i+1];
	}

	ans[0] = 2;
}

int64 solve(int N){
	return ans[N - 1];
}

int main(){

	pre_solve();

	int T, N;
	scanf("%d",&T);
	while(T--){
		scanf("%d",&N);
		printf("%lld\n", solve(N));
	}

	return 0;
}