题解：这个题目看着挺吓人的，如果仔细想想的话，应该能想出来。题解还是挺好的理解的。

首先设gcd(a1,a2,a3…an)=i，那么a1~an一定是i的倍数，所以ai一共有k/i种取值。有n个数，所有就有(k/i)^n种情况。光是这样还是不行的，因为a1~an的gcd可能为j*i。所以我们要减去2*i,3*i……j*i<=k。倒着来就可以了，复杂度应该是o(nlogn)

code：

#include
using namespace std;
typedef long long ll;
const ll N=1e5+;
const ll MOD=1e9+;
ll dp[N];
ll ksm(ll x,ll y){
ll res=;
while(y){
if(y&) res=res*x%MOD;
x=x*x%MOD;
y>>=;
}
return res%MOD;
}
int main(){
ll n,k;
cin>>n>>k;
ll ans=;
for(ll i=k;i>=;i--){
dp[i]=ksm(k/i,n);
for(ll j=*i;j<=k;j+=i) dp[i]=(dp[i]-dp[j]+MOD)%MOD;
ans=(ans+i*dp[i]+MOD)%MOD;
}
cout<<ans<<endl;
return ;
}