( ext{Solution:})
[sum_{d=1}^nd^ksum_{i=1}^frac{n}{d}sum_{j=1}^frac{n}{d}[gcd(i,j)=1]
]
[=sum_{d=1}^n d^ksum_{x=1}^frac{n}{d}mu(x)lfloorfrac{n}{xd}
floorlfloorfrac{m}{xd}
floor
]
[=sum_{T=1}^nsum_{d|T}d^kmu(frac{T}{d})lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor
]
[f(T)=sum_{d|T}d^kmu(frac{T}{d})
]
[Ans=sum_{T=1}^nf(T)lfloorfrac{n}{T}
floorlfloorfrac{m}{T}
floor
]
考虑(f(T):)
[f(T)=sum_{d|T}d^kmu(frac{T}{d})
]
[T=id_k*mu
]
令(h(x)=mu(x),f(x)=id_k*h)
对于(xin prime:)
(h(x)=-1,f(x)=-1+p^k)
对于(xin p^n:)
(h(x)=0,f(x)=p^{nk}-p^{nk-k})
于是线性筛(f(T).)
对(T)进行整除分块可以做到单次(O(sqrt{n}))的复杂度。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int MAXN=5e6+10;
char buf[1<<21],*p1=buf,*p2=buf;
inline int read(){
int s=0;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch)){
s=s*10+ch-'0';
ch=gc();
}
return s;
}
inline int add(int x,int y){return (x+y+mod)%mod;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
int T,k,pk[MAXN];
int p[MAXN],cnt,f[MAXN];
bitset<MAXN>vis;
inline int qpow(int a,int b){
int res=1;
while(b){
if(b&1)res=mul(res,a);
a=mul(a,a);b>>=1;
}
return res;
}
void predo(){
int N=5000000;f[1]=1;
for(int i=2;i<=N;++i){
if(!vis[i])p[++cnt]=i,pk[cnt]=qpow(i,k),f[i]=pk[cnt]-1,f[i]+=mod,f[i]%=mod;
for(int j=1;j<=cnt&&i*p[j]<=N;++j){
vis[i*p[j]]=1;
if(i%p[j]==0){
f[i*p[j]]=mul(f[i],pk[j]);
break;
}
f[i*p[j]]=mul(f[i],f[p[j]]);
}
}
for(int i=2;i<=N;++i)f[i]=add(f[i-1],f[i]);
}
int solve(int n,int m){
int res=0,N=min(n,m);
for(int l=1,r;l<=N;l=r+1){
r=min((n/(n/l)),(m/(m/l)));
res=add(res,mul(f[r]-f[l-1]+mod,mul(n/l,m/l)+mod));
}
return res;
}
signed main(){
T=read(),k=read();
predo();
while(T--){
int n,m;
n=read(),m=read();
printf("%lld
",solve(n,m));
}
return 0;
}