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

题目链接

题解

莫比乌斯反演

记

假设$\exists i,j,b_j<b_i(i̸=j)$，那么对于$a_i$无论是$b_i$还是$b_i-1$，对$f$值没有任何影响，而对$\mu$值是$-1$和$1$的区别，因此此时$g(T)=0$。

否则，存在一个特殊情况

代码

#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=10000000;int p[maxn+10],prime[maxn+10],cnt,low[maxn+10],num[maxn+10],f[maxn+10];int getprime(){
     p[1]=num[1]=1;  low[1]=f[1]=0;  for(int i=2; i<=maxn; ++i)    {
         if(!p[i])        {
             prime[++cnt]=i;          low[i]=num[i]=f[i]=1;        }      for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j)        {
             int x=i*prime[j];          p[x]=1;          if(i%prime[j]==0)            {
                 low[x]=low[i]+1;              num[x]=num[i];              if(num[x]==1)                {
                     f[x]=1;                }              else                {
                     f[x]=(low[x]==low[num[x]])?-f[num[x]]:0;                }              break;            }          low[x]=1;          num[x]=i;          f[x]=(low[x]==low[i])?-f[i]:0;        }    }  for(int i=2; i<=maxn; ++i)    {
         f[i]+=f[i-1];    }  return 0;}int T,n,m;int main(){
     getprime();  T=read();  while(T--)    {
         n=read();      m=read();      long long 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+=1ll*(f[r]-f[l-1])*(n/l)*(m/l);        }      printf("%lld\n",ans);    }  return 0;}
    
   

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