传送门

题意：

给出一个n个数的数列 ai​ a i ​ ,考虑其中所有gcd大于1的集合，每个集合的贡献是gcd乘上集合的大小，求这个数列的总贡献%1e9+7

(1 ≤ n ≤ 200000,1 ≤ ai ≤ 1000000) ( 1   ≤   n   ≤   200000 , 1   ≤   a i   ≤   1000000 )

Solution:

一开始一直在想与n有关的复杂度的算法没想到最后跟a的大小有关…

遇到这种需要求有关集合这种dp和数据结构都不好使的题，我们需要想到用容斥和组合数来求！！！

我们用cnt[i]来表示a中是i的倍数的数的个数

f[i]表示gcd为i的集合中的元素总个数

想求出f[i],我们可以先考虑gcd为i的倍数的集合中的元素总个数： ∑x∈Ssize(x),(size(S)==cnt[i]) ∑ x ∈ S s i z e ( x ) , ( s i z e ( S ) == c n t [ i ] )

即为 ∑cnt[i]i−0i∗C(cnt[i],i)=cnt[i]∗2cnt[i]−1 ∑ i − 0 c n t [ i ] i ∗ C ( c n t [ i ] , i ) = c n t [ i ] ∗ 2 c n t [ i ] − 1

然后我们再把gcd为2i,3i,4i…的数减去，就可以得到f[i]了：

f[i]=cnt[i]∗2cnt[i]−1−f[2i]−f[3i]−... f [ i ] = c n t [ i ] ∗ 2 c n t [ i ] − 1 − f [ 2 i ] − f [ 3 i ] − . . .

最后的答案即为 ∑maxai=2i∗ans[i] ∑ i = 2 m a x a i ∗ a n s [ i ]

递推即可，复杂度 O(maxa+maxa2+maxa3+...)=O(maxalogmaxa) O ( m a x a + m a x a 2 + m a x a 3 + . . . ) = O ( m a x a log ⁡ m a x a )

代码很简洁：

#include<cstdio>
#include<iostream>
using namespace std;
int n,maxn;
int a[1000010];
const int mod=1e9+7;
int f[1000010];
int x,mi[200010];
int ans=0;
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&x),a[x]++,maxn=max(maxn,x);
    mi[0]=1;
    for (int i=1;i<=n;i++) mi[i]=mi[i-1]*2%mod;
    for (int i=maxn;i>1;i--)
    {
        int cnt=0;
        for (int j=i;j<=maxn;j+=i) cnt+=a[j];
        if (cnt)
        {
            f[i]=1ll*cnt*mi[cnt-1]%mod;
            for (int j=i+i;j<=maxn;j+=i) f[i]=(f[i]-f[j]+mod)%mod;
            ans=(1ll*ans+1ll*i*f[i])%mod;
        }
    }
    printf("%d",ans);
}