本文共 1882 字，大约阅读时间需要 6 分钟。

题目链接

题解

反演

代码

#include 
   
    #include 
    
     int read(){
     int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {
         if(ch=='-')        {
             f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {
         x=x*10+ch-'0';      ch=getchar();    }  return x*f;}const int maxn=5000000;const int mod=1000000007;int quickpow(int a,int b){
     int res=1;  while(b)    {
         if(b&1)        {
             res=1ll*res*a%mod;        }      a=1ll*a*a%mod;      b>>=1;    }  return res;}int k,p[maxn+10],prime[maxn+10],cnt,f[maxn+10];int getprime(){
     p[1]=f[1]=1;  for(int i=2; i<=maxn; ++i)    {
         if(!p[i])        {
             prime[++cnt]=i;          f[i]=quickpow(i,k)-1;          if(f[i]<0)            {
                 f[i]+=mod;            }        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
             int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                 f[x]=1ll*(f[prime[j]]+1)*f[i]%mod;              break;            }          f[x]=1ll*f[prime[j]]*f[i]%mod;        }    }  for(int i=1; i<=maxn; ++i)    {
         f[i]+=f[i-1];      if(f[i]>=mod)        {
             f[i]-=mod;        }    }  return 0;}int T,n,m;int main(){
     T=read();  k=read();  getprime();  while(T--)    {
         n=read();      m=read();      int ans=0;      for(int l=1,r; l<=std::min(n,m); l=r+1)        {
             r=std::min(n/(n/l),m/(m/l));          ans=(ans+1ll*(f[r]-f[l-1]+mod)*(n/l)%mod*(m/l))%mod;        }      printf("%d\n",ans);    }  return 0;}
    
   

转载地址：https://blog.csdn.net/wang3312362136/article/details/85990485 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！