Codeforces ECR #036 : G. Coprime Arrays

途中手間取りすぎて時間切れ。
http://codeforces.com/contest/915/problem/G

問題

f(N,i)を以下のように定める。

• N要素の整数列で、各要素は1～iの間の値を取る
• 全要素のGCDは1

N,Kが与えられるので、f(N,1)～f(N,K)を求めよ。

解法

f(N,1)から順に(N,x)を求めることを考える。
全要素が(x-1)以下のケースはf(N.x-1)ですでに求めているので、最低1要素xを含むケースを考えよう。

xの素因数の集合P(x)を求めたら、包除原理を用いてP(x)中のいくつかの要素を素因数とする数列の組み合わせの数を足し引きしていこう。
なお、最低1つはxを含まなければいけないので、全部が(x-1)以下となるケースを同様に求めて引くとよい。

int N,K;
ll mo=1000000007;
ll B[2020200];

const int prime_max = 2100000;
vector<int> P[2020202];
int po[2020202];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	for(i=1;i<=2020000;i++) {
		po[i]=modpow(i,N);
		if(i>1 && P[i].empty()) {
			for(j=i;j<2020000;j+=i) P[j].push_back(i);
		}
	}
	
	
	ll ret=0;
	int tot=0;
	for(i=1;i<=K;i++) {
		B[i]=(B[i-1]+po[i]-po[i-1]+mo)%mo;
		
		for(int mask=1;mask<1<<P[i].size();mask++) {
			int v=1;
			int s=1;
			FOR(j,P[i].size()) if(mask&(1<<j)) s=-s,v*=P[i][j];
			B[i]+=s*(po[i/v]-po[i/v-1]);
		}
		
		B[i]=(B[i]%mo+mo)%mo;
		ret += B[i]^i;
	}
	cout<<ret%mo<<endl;
}

まとめ

包除原理の問題、少し慣れてきた気がする。