AtCoder ABC #162 : E - Sum of gcd of Tuples (Hard)

まぁこれは典型かな…。
https://atcoder.jp/contests/abc162/tasks/abc162_e

問題

整数N,Kが与えられる。
1～Kの整数N個なら数列を考えると、その数列はK^N通りある。
各数列におけるGCDの和を答えよ。

解法

f(i) := 数列のGCDがiとなる数列の組み合わせ
が求められれば、解はsum(i*f(i))である。
それにあたり、
g(i) := 数列のGCDがiの倍数となる数列の組み合わせ
を考えよう。これは各要素がiの倍数であればいいのでfloor(K/i)^N通りである。
ここからiより大きなiの倍数のケースを除けばいいので、
f(i)=g(i)-f(2*i)-f(3*i)-...
となる。よってf(i)は大きな順に求めていくとよい。

ll mo=1000000007;
int N,K;
ll dp[101010];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	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;
	ll sum=0;
	for(i=K;i>=1;i--) {
		dp[i]=modpow(K/i,N);
		for(j=i*2;j<=K;j+=i) dp[i]-=dp[j];
		dp[i]=(dp[i]%mo+mo)%mo;
		sum+=i*dp[i]%mo;
	}
	cout<<sum%mo<<endl;
}

まとめ

このぐらいの問題、Dで出るかと思ったらEなのね。