欧拉反演

数学知识

因子个数

CF1900D small GCD

题意：
给定一个数组 $ a ,f(a,b,c)表示三个数排序后,a<=b<=c , 等于gcd(a,b)的值,求 \sum _{i=1}^{N} \sum _{j=i+1}^{N} \sum _{k=j+1}^{N}f(a_i,a_j,a_k) $
思路： $ 对数组排序,转换得—> \sum _{i=1}^N \sum _{j=i+1}^N gcd(a_i,a_j)*(n-j)$

另类做法

• 预处理出来所有数的因子 $ O(nlogn) ,n=1e5$
• 枚举每个a，将可能的gcd放入n-j $ O(128n) $
• 枚举每一个gcd,用cnt记录前面gcd出现的次数，表示当前数可以和前面的一个数组成当前的gcd的合法对数，即当前为j,cnt为i的个数
• 最后容斥一下,将当前gcd的答案减去其倍数 $ O(mlogm) m为最大值$

  void init(){//预处理因数
    for(int i=1;i<=1e5;i++){
        for(int j=i;j<=1e5;j+=i)factor[j].push_back(i);
    }
  }
  void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    int m=0;//m为最大值
    for(int i=1;i<=n;i++)cin>>a[i],m=max(m,a[i]);
    sort(a.begin()+1,a.end());
    vector<ll> b[m+1],ans(m+1);//b存可能的j值，ans存答案
    for(int i=1;i<=n;i++){
        for(auto x:factor[a[i]])b[x].push_back(n-i);
    } 
    for(int i=1;i<=m;i++){//计算答案
        int cnt=0;
        for(auto x:b[i]){
            ans[i]+=x*(cnt++);
        }
    }
    for(int i=m;i>=1;i--){//容斥
        for(int j=2*i;j<=m;j+=i)ans[i]-=ans[j];
    }
    ll res=0;
    for(int i=1;i<=m;i++)res+=ans[i]*i;//乘上本身gcd
    cout<<res<<"\n";
  }
  

  莫反做法

  $ \sum _{d|x} \phi(d)=x $
  $ 转化为 \sum _{i=1}^N \sum _{j=1}^{i-1} \sum _{d|a_i,a_j} \phi(d)*(n-i) $
  枚举a[i]的因子,记录之前出现的因子个数,答案即为phi[d]*cnt[d]，最后统一乘上(n-i)
  $ 复杂度：O(n \sqrt n) $

  int phi[N],prime[N];
  void init(){
    phi[1]=1;
    int m=0;
    for(int i=2;i<=1e5;i++){
        if(!phi[i]){
            prime[++m]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=m&&prime[j]*i<=1e5;j++){
            if(i%prime[j]==0){
                phi[prime[j]*i]=phi[i]*prime[j];
                break;
            }
            phi[prime[j]*i]=phi[i]*phi[prime[j]];
        }
    }
  }
  void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    int m=0;
    for(int i=1;i<=n;i++)cin>>a[i],m=max(m,a[i]);
    sort(a.begin()+1,a.end());
    vector<int> cnt(m+1);
    ll ans=0;
    for(int i=1;i<n;i++){
        ll res=0;
        for(int d=1;d<=a[i]/d;d++){
            if(a[i]%d)continue;
            res+=1ll*phi[d]*(cnt[d]++);
            if(d*d!=a[i])res+=1ll*phi[a[i]/d]*(cnt[a[i]/d]++);
        }
        ans+=res*(n-i);
    }
    cout<<ans<<"\n";
  }