题意

给一个元素个数为$n$的集合，告诉集合中每个元素是什么。对于其每个子集，若$gcd(a_1,a_2, \cdots ,a_k) > 1 $ (其中$a_1,a_2, \cdots ,a_k$为该子集中的所有元素) 则该子集产生价值为$k \times gcd(a_1,a_2, \cdots ,a_k)$ 。求所有子集的价值和。

思路

考虑枚举$gcd$，如果集合中有$k$个数为$gcd$的倍数，那么该$gcd$对答案的贡献为$gcd \times (1 \times C_k^1 + 2 \times C_k^2 + \cdots +k \times C_k^k)$。
由二项式定理得
$$(1+x)^n=1+\sum\limits_{i=1}^nx^iC_n^i$$
两边对$x$求导可得
$$n(1+x)^{n-1}=\sum\limits_{i=1}^n ix^{i-1}C_n^i$$
将$x=1$代入得
$$n \times 2^{n-1}=\sum\limits_{i=1}^n i C_n^i$$
预处理出$2$的$n$次方后，我们便能对每个$gcd$在$O(1)$的时间内求出对答案的贡献值。
然而，这还有个问题，便是会重复计算，因此我们还需再用容斥原理算一下对答案的贡献。
比赛中推出了上面的做法，然而算错了时间复杂度，没敢写。。。也是醉了。
枚举$gcd$的时间复杂度为$O(n)$，容斥的时间复杂度为$O(log n)$，所以总时间复杂度为$O(nlog n)$。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=1000000;
typedef long long ll;
const ll mod=1e9+7LL;
int n;
ll num[Nmax+10];
ll powe[Nmax+10];
void init()
{
    powe[0]=1LL;
    for(int i=1;i<=Nmax;i++)
        powe[i]=(powe[i-1]<<1)%mod;
}
int main()
{
    #ifdef test
    #endif
    //freopen("d.in","r",stdin);
    init();
    scanf("%d",&n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        num[x]++;
    }
    for(int i=1;i<=Nmax;i++)
        for(int j=i<<1;j<=Nmax;j+=i)
            num[i]+=num[j];
     for(int i=1;i<=Nmax;i++)
         if(num[i])
            num[i]=num[i]*powe[ num[i]-1 ]%mod;
     ll ans=0LL;
     for(int i=Nmax;i>1;i--)
     {
         for(int j=i<<1;j<=Nmax;j+=i)
             num[i]=(num[i]-num[j]+mod)%mod;
         ans=(ans+num[i]*i%mod)%mod;
     }
     printf("%lld\n",(ans+mod)%mod);
     return 0;
}