【bzoj4407】【于神之怒加强版】【莫比乌斯反演】

Description

i=1nj=1mgcd(i,j)kmod(109+7)

Input

Output

Sample Input

1 2
3 3
Sample Output

20
HINT

1<=N,M,K<=5000000,1<=T<=2000

d=1ndki=1ndnidmidu(i)

T=1nnTmTd|Tdku(Td)

#include<iostream>#include<cstdio>#include<cstring>#define N 5000010#define P 1000000007 #define LL long longusing namespace std;int T,k,p[N],f[N],pos;LL n,m,g[N],u[N],ans;LL power(LL a,int b){ LL ans;a%=P; for (ans=1;b;a=a*a%P,b>>=1) if (b&1) ans=ans*a%P; return ans;}void pre(){  u[1]=1;g[1]=1;  for (int i=2;i<=n;i++){   if (!f[i]){p[++p[0]]=i;u[i]=-1;g[i]=(power(i,k)-1+P)%P;}   for (int j=1;j<=p[0]&&i*p[j]<=n;j++){    f[i*p[j]]=1;     if (i%p[j]==0){g[i*p[j]]=g[i]*power(p[j],k)%P;break;}    u[i*p[j]]=-u[i];g[i*p[j]]=(g[i]*g[p[j]])%P;   }   }  for (int i=1;i<=n;i++) g[i]=(g[i]+g[i-1])%P;}int main(){ scanf("%d%d",&T,&k);n=N-10;pre(); while (T--){  scanf("%d%d",&n,&m);  if (n>m) swap(n,m);ans=0;pos=0;   for (int i=1;i<=n;i=pos+1){    pos=min(n/(n/i),m / (m / i));    ans+=(LL)(n / i)*(LL)(m / i)%P*(LL)(g[pos]-g[i-1]+P)%P;    ans%=P;  }  printf("%lld\n",ans);   }  }

## 关于作者

白红宇是个全栈工程师，前端vue，小程序，app开发到后端框架设计，数据库设计，环境部署上线运维。