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

题目链接

题解

反演得到

容易发现$F(a,b)$只有在$a\le b$时才有值，因此只要两个数$x,y$，$\mu (x)=0$或$\mu (y)=0$或$\mathrm{l}\mathrm{c}\mathrm{m}(x,y)>\max (A,B,C)$，那么在枚举过程中$d,e,f$中任意两个$=x$和$y$，这次枚举就一定没有贡献了。

因此可以对于每个$\mu (x)$和$\mu (y)$都不等于$0$并且$\mathrm{l}\mathrm{c}\mathrm{m}(x,y)\le \max (A,B,C)$时，在$x,y$间连一条权值为$\mathrm{l}\mathrm{c}\mathrm{m}(x,y)$边，那么对答案能产生贡献的就是这张图里面所有的三元环。

为了让建边不变成$O(n^2)$的，考虑枚举边权，由于$\mu (x)$和$\mu (y)$都$̸=0$，因此边权的$\mu$也不会$=0$，那么边权就一定可以拆成多个不同质因子之积。枚举这些质因子的子集作为$x$，枚举$x$的所有质因子的子集作为$\gcd (x,y)$，容易得到$y$，那么在$x$和$y$间连一条边即可。

容(shi)易(ji)发(shang)现，这张图其实是稀疏的，边数不会很大。

因此$O(m\sqrt{m})$的枚举三元环即可。

复杂度$O($玄学$)$。（可能）需要一些卡常技巧。

代码

#include 
   
    #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=100000;const int maxm=1000000;const int mod=1000000007; int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10];std::vector
      
        d[maxn+10]; int getprime(){
     p[1]=mu[1]=1;  for(int i=2; i<=maxn; ++i)    {
         if(!p[i])        {
             prime[++cnt]=i;          mu[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)            {
                 mu[x]=0;              break;            }          mu[x]=-mu[i];        }    }  for(int i=1; i<=cnt; ++i)    {
         for(int j=1; j<=maxn/prime[i]; ++j)        {
             (mu[prime[i]*j])&&(d[prime[i]*j].push_back(prime[i]),0);        }    }  return 0;} int getf(int *f,int b){
     for(int i=1; i<=b; ++i)    {
         for(int j=i; j<=b; j+=i)        {
             f[i]+=b/j;          if(f[i]>=mod)            {
                 f[i]-=mod;            }        }    }  return 0;} struct edge{
     int x,y,v;   edge(int _x=0,int _y=0,int _v=0):x(_x),y(_y),v(_v){
   }}; int T,A,B,C,fa[maxn+10],fb[maxn+10],fc[maxn+10],deg[maxn+10],cnte,tmp[maxn+10];edge all[maxm+10];std::vector
       
         e[maxn+10]; int main(){
     getprime();  T=read();  while(T--)    {
         A=read();      B=read();      C=read();      (B
        
         =0; k=(k-1)&j) { int g=1; for(int l=0; l
         
          deg[all[i].y]) ||((deg[all[i].x]==deg[all[i].y])&&(all[i].x
          
           ::iterator a=e[i].begin(); a!=e[i].end(); ++a) { tmp[a->y]=a->v; } for(std::vector
           
            ::iterator a=e[i].begin(); a!=e[i].end(); ++a) { for(std::vector
            
             ::iterator b=e[a->y].begin(); b!=e[a->y].end(); ++b) { (tmp[b->y])&& (((ans=(ans+mu[i]*mu[a->y]*mu[b->y] *(1ll*fa[a->v]*fb[b->v]*fc[tmp[b->y]] +1ll*fa[a->v]*fb[tmp[b->y]]*fc[b->v] +1ll*fa[b->v]*fb[a->v]*fc[tmp[b->y]] +1ll*fa[b->v]*fb[tmp[b->y]]*fc[a->v] +1ll*fa[tmp[b->y]]*fb[a->v]*fc[b->v] +1ll*fa[tmp[b->y]]*fb[b->v]*fc[a->v]))%mod)<0)&&(ans+=mod)); } } for(std::vector
             
              ::iterator a=e[i].begin(); a!=e[i].end(); ++a) { tmp[a->y]=0; } } for(int i=1; i<=A; ++i) { for(std::vector
              
               ::iterator a=e[i].begin(); a!=e[i].end(); ++a) { ((ans=(ans+mu[i]*(1ll*fa[a->v]*fb[a->v]*fc[a->y] +1ll*fa[a->v]*fb[a->y]*fc[a->v] +1ll*fa[a->y]*fb[a->v]*fc[a->v]) +mu[a->y]*(1ll*fa[a->v]*fb[a->v]*fc[i] +1ll*fa[a->v]*fb[i]*fc[a->v] +1ll*fa[i]*fb[a->v]*fc[a->v]))%mod)<0)&&(ans+=mod); } } for(int i=1; i<=A; ++i) { ((ans=(ans+mu[i]*1ll*fa[i]*fb[i]*fc[i])%mod)<0)&&(ans+=mod); } printf("%d\n",ans); for(int i=1; i<=A; ++i) { fa[i]=0; } for(int i=1; i<=B; ++i) { fb[i]=0; } for(int i=1; i<=C; ++i) { fc[i]=0; } for(int i=1; i<=A; ++i) { deg[i]=0; } for(int i=1; i<=A; ++i) { e[i].clear(); } cnte=0; } return 0;}
              
             
            
           
          
         
        
       
      
     
    
   

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