ABC - 162 - E - Sum of gcd of Tuples (Hard) （DP&数论)

ABC - 162 - E - Sum of gcd of Tuples (Hard) （DP&数论)

思路：

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9+7;
ll ksm(ll a,ll b){//快速幂 
	ll ans=1;
	while(b){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
ll f[N],ans=0;
int main(){	
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=k;i>=1;i--){ //倒序遍历dp 
		f[i]=ksm(k/i,n);
		for(int j=i+i;j<=k;j+=i)
			f[i]=(f[i]-f[j]+mod)%mod;
		ans=(ans+f[i]*i)%mod; 
	}
	printf("%lld\n",ans);
	return 0;
}