题目链接： 点击这里
首先哦，令n<=m，我们来化简式子：
[sum_{i=1}^nsum_{j=1}^mgcd(i,j)^k
]
设gcd(i,j)=d，则可以变成这样:
[sum_{i=1}^nsum_{j=1}^md^k\
]
把d提到前面去，来枚举d：
[sum_{d=1}^nd^ksum_{i=1}^{lfloor{frac{n}{d}}
floor}sum_{j=1}^{lfloor{frac{m}{d}}
floor}[gcd(i,j)=1]
]
然后就可以开始套了
[sum_{d=1}^nd^ksum_{i=1}^{lfloor{frac{n}{d}}
floor}sum_{j=1}^{lfloor{frac{m}{d}}
floor}sum_{x|i,x|j}mu(x)
]
然后找到满足条件的x的个数，就可以和前面两个sigma说再见了
[sum_{d=1}^nd^ksum_{x=1}^{lfloor{frac{n}{d}}
floor}mu(x)lfloor{frac{n}{dx}}
floorlfloor{frac{m}{dx}}
floor\
设T=dx，再来枚举T\
sum_{d=1}^nd^ksum_{x=1}^{lfloor{frac{n}{d}}
floor}mu(frac{T}{d})lfloor{frac{n}{T}}
floorlfloor{frac{m}{T}}
floor\
sum_{T=1}^nlfloor{frac{n}{T}}
floorlfloor{frac{m}{T}}
floorsum_{d|T}d^kmu(frac{T}{d})
]
一般的题到这一步就能直接搞了，然而会T，所以我们来继续推：
注：以下受@hby大佬的启发，与本人博客差不多
设
[f(T)=sum_{d|T}d^kmu(frac{T}{d})\
g(T)=T^k
]
看！(f(T))是不是(mu)和(g)的卷积形式！所以(f)是个积性函数!
我们来对(f(x))进行讨论，首先我们将(x)分解质因数
[x=prod{p_i^{a_i}},p_iinmathbb{P}\
f(x)=prod{f(p_i^{a_i})}\
f(p_i^{a^i})=sum_{d|p_i^{a_i}}d^kmu(frac{p_i^{a_i}}{d})\
因为p_i是个质数，所以\
f(p_i^{a_i})=sum_{j=0}^{a_i}{p_i}^{jk}mu(p_i^{a_i-j})\
再考虑一下mu的性质，可以得出只有当j=a_i或j=a_i-1时，mu不为0，于是\
f(p_i^{a_i})=p_i^{a_ik}-p_i^{(a_i-1)k}\
pinmathbb{P}，于是对于f(xp)，若p|x，则只是多了几个指数而已，那么f(xp)=f(x)*p^k\
否则，就是添加了几个质因数，则f(xp)=f(x)*(p^k-1)
]
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+1;
const int pps=1e9+7;
int n,m,k,t,tot;
int pri[N],mu[N],vis[N],p[N],f[N];
int quick(int a,int b){
int sum=1;
while(b){
if(b&1) sum*=a,sum%=pps;
a=(a*a)%pps,b>>=1;
}return sum%pps;
}
void prepare(){
f[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]) pri[++tot]=i,p[tot]=quick(i,k),f[i]=p[tot]-1;
for(int j=1;j<=tot&&pri[j]*i<=N;j++){
vis[i*pri[j]]=1;
if(!(i%pri[j])){
f[i*pri[j]]=f[i]*p[j]%pps;
break;
}f[i*pri[j]]=f[i]*(p[j]-1)%pps;
}
}for(int i=1;i<=N;i++) f[i]=(f[i]+f[i-1])%pps;
}
int calc(int n,int m){
int d=1,sum=0;
while(d<=n&&d<=m){
int pre=d;d=min(n/(n/d),m/(m/d));
sum=(sum+(n/d)*(m/d)%pps*(f[d]-f[pre-1])%pps)%pps;
++d;
}return (sum+pps)%pps;
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
t=read(),k=read();
prepare();
while(t--){
n=read(),m=read();
printf("%lld
",calc(n,m));
}
return 0;
}