#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 5000005
ll n,m,K;
ll Pow(ll a,ll b){
ll res=
1;
while(b){
if(b%
2)res=res*a%
mod;
b>>=
1;a=a*a%
mod;
}
return res;
}
bool vis[maxn];
ll prime[maxn],G[maxn],sum[maxn],mu[maxn],mm;
void init(){
mu[1]=G[
1]=
1;
for(
int i=
2;i<maxn;i++
){
if(!
vis[i]){
prime[++mm]=
i;
mu[i]=-
1;
G[i]=Pow(i,K)-
1;
if(G[i]<
0)G[i]+=
mod;
}
for(
int j=
1;j<=mm;j++
){
if(i*prime[j]>=maxn)
break;
vis[i*prime[j]]=
1;
if(i%prime[j]==
0){
mu[i*prime[j]]=
0;
G[i*prime[j]]=G[i]*Pow(prime[j],K)%
mod;
break;
}
else {
mu[i*prime[j]]=-
mu[i];
G[i*prime[j]]=G[i]*G[prime[j]]%
mod;
}
}
}
for(
int i=
1;i<maxn;i++
)
sum[i]=(sum[i-
1]+G[i])%
mod;
}
int main(){
int t;cin>>t>>
K;
init();
while(t--
){
cin>>n>>
m;
if(n>
m)swap(n,m);
ll ans=
0;
for(
int l=
1,r;l<=n;l=r+
1){
r=min(n/(n/l),m/(m/
l));
ll tmp=((sum[r]-sum[l-
1])%mod+mod)%
mod;
ans=(ans+tmp*(n/l)%mod*(m/l)%mod)%
mod;
}
cout<<ans<<
'\n';
}
}
转载于:https://www.cnblogs.com/zsben991126/p/11152863.html
