Codeforces Round #428 (Div. 2)：D. Winter is here（组合数公式） +容斥

参考http://m.blog.csdn.net/Hallelujah520/article/details/77164467

和http://m.blog.csdn.net/Hallelujah520/article/details/77164467

要容斥是因为这个地方算的是组合数的公式，所以有些地方的gcd是4，不是2的情况

差的地方：

1：这个地方的公式不会推。。

2：对于这个地方的容斥，想不到还能这样处理，而且这个复杂度不会爆。。。

不敲了，直接复制别人的代码。。

#include<stdio.h>  
    #define mod 1000000007  
    #define LL long long  
    LL cnt[], sum[];  
    LL Pow(LL a, LL b)  
    {  
        LL now;  
        now = ;  
        while(b)  
        {  
            if(b%)  
                now = now*a%mod;  
            a = a*a%mod;  
            b /= ;  
        }  
        return now;  
    }  
    int main(void)  
    {  
        LL ans, i, j, n, x;  
        scanf("%lld", &n);  
        for(i=;i<=n;i++)  
        {  
            scanf("%lld", &x);  
            cnt[x]++;  
        }  
        ans = ;  
        for(i=;i>=;i--)  
        {  
            x = ;  
            for(j=i;j<=;j+=i)  
            {  
                sum[i] -= sum[j];  
                x += cnt[j];  
            }  
            sum[i] += x*Pow(, x-)%mod;  
            ans = ((ans+sum[i]*i)%mod+mod)%mod;  
        }  
        printf("%lld\n", ans);  
        return ;  
    }