upd on 2022-7-13： 修改若干不合适叙述。
一、题意
很明了，给出 \(n,k\)，求下面这个复杂式子的值：
\[\sum_{a_1=1}^k\sum_{a_1=1}^k\cdots\sum_{a_{n-1}=1}^k\sum_{a_n=1}^k\gcd\left\{a_i\right\} \]二、思路
一眼莫反，但是个人觉得有点小题大做。
首先我们要认识到，\(\gcd\left\{a_i\right\}\leq k\)，结合 \(k\le10^5\)，所以可以令 \(f_j\) 表示 \(\gcd\left\{a_i\right\}=j\) 的次数，就很好做很好想了。
如果要让 \(\gcd\left\{a_i\right\}=mj\)，则 \(\forall a_i=nk\) （此处 \(n,m\) 为正整数），易得 \(\forall a_i\) 有 \(\lfloor\dfrac k j\rfloor\) 种取值，共 \(\lfloor \dfrac k i\rfloor^n\) 种可能。
注意是 \(mj\) 而不是 \(j\)，此时 \(f_j\) 不是我们想要的答案，有重复，所以要去重：
for(y=x<<1;y<=k;y+=x)
f[x]=(f[x]-f[y]+mod)%mod;
为了去重和转移的方便，倒序枚举 \(i\)，复杂度 \(O\left(k\log k\log n\right)\)，比莫反慢得多，但是可以忍受。
三、代码
#include <stdio.h>
const int mod=1000000007;//对1e9+7取模
long long n,k,i,x,y,ans;
long long f[100005];
long long repow(long long a,long long b){//快速幂
long long ans=1,base=a;
while(b){
if(b&1)
ans=((ans%mod)*(base%mod))%mod;
base=((base%mod)*(base%mod))%mod;
b>>=1;
}
return ans;
}
int main(){
scanf("%lld %lld",&n,&k);
for(x=k;x;--x){//倒序枚举
f[x]=repow(k/x,n);
for(y=x<<1;y<=k;y+=x)
f[x]=(f[x]-f[y]+mod)%mod;//去重
ans=(ans+x*f[x]%mod)%mod;//计算答案
}
printf("%lld",ans);//输出
return 0;
}