Input
输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。
Output
如题
Sample Input1 2 3 3 Sample Output20 Hint
1<=N,M,K<=5000000,1<=T<=2000
设f(n)=nkf(n)=nk,则FF为ff和μμ的狄利克雷卷积。
对于FF的计算,质数时直接快速幂,质数的幂递推计算,其它数可以通过线性筛得到。
对于每次询问,分块求和即可。
时间复杂度O(n+T√n)
#include<bits/stdc++.h> const int N=5000001,P=1000000007; int T,n,m,i,j,k,tot,p[N],f[N],g[N],F[N],ans;bool v[N]; inline int pow(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;} inline int min(int a,int b){return a<b?a:b;} int main(){ scanf("%d%d",&T,&k); for(F[1]=1,i=2;i<N;i++){ if(!v[i])f[i]=pow(i,k),g[i]=i,F[i]=f[i]-1,p[tot++]=i; for(j=0;j<tot&&i*p[j]<N;j++){ v[i*p[j]]=1; if(i%p[j]){ g[i*p[j]]=p[j]; F[i*p[j]]=1LL*F[i]*F[p[j]]%P; }else{ g[i*p[j]]=g[i]*p[j]; F[i*p[j]]=g[i]!=i?1LL*F[i/g[i]]*F[g[i]*p[j]]%P:1LL*F[i]*f[p[j]]%P; break; } } } for(i=2;i<N;i++)F[i]=(F[i-1]+F[i])%P; while(T--){ scanf("%d%d",&n,&m); for(ans=0,i=1;i<=n&&i<=m;i=j+1){ j=min(n/(n/i),m/(m/i)); ans=(1LL*(F[j]-F[i-1]+P)*(n/i)%P*(m/i)+ans)%P; } printf("%d\n",ans); } return 0; }