CodeForces 839 D Winter is here(反発原理)

タイトルリンク:http://codeforces.com/problemset/problem/839/D
题意:n人の兵士がいて、各兵士の力の値はa[i]で、今入力の顺番によってkの数(つまりi、i+1、i+3、i+j.....i+k)を选んで、このkの数の最大公约数が1より大きくて、そしてgcd*kを计算して、それからこれらのgcd*kに対して和を求めます
構想:エーステナイトふるいの原理を利用して、a[j]の配列の中でどれだけのiの倍数があるかを求めて、x個の数がiの倍数であると仮定して、このx個のiの倍数の配列はx*2^(x-1)PSがあります:第1の数が配列の中に存在すると仮定して、その他のx-1の要素は2種類の選択があって、選ぶか選ばないか、だからx*2^(x-1)個が配列します.しかし2,4,8については4と8はともに2の倍数であるがgcd(4,8)=4であるため,2の倍数を計算する際にはこの配列を外す.

#include 
#define LL long long
using namespace std;

const int N = 1000010;
const int mod = 1e9 + 7;
int n,a[N];
LL dp[N],f[N];

void init(){
    f[0] = 1;
    for(int i = 1; i < N; i ++) f[i] = 2 * f[i-1] % mod;
}

int main(){
    init();
    scanf("%d",&n);
    int num;
    for(int i = 0; i < n; i ++) scanf("%d",&num), a[num] ++;
    LL ans = 0;
    for(int i = N-1; i > 1; i --){
        LL x = 0;
        for(int j = i; j < N; j += i) x += a[j];//  i       
        if(x){
            dp[i] = x * f[x-1] % mod;//      x   ，        x * 2^(x-1) 
            for(int j = i+i; j < N; j += i) dp[i] = (dp[i] - dp[j] + mod) % mod;//    ，     
        }
        ans = (ans + 1LL * i * dp[i]) % mod;
    }
    printf("%I64d
",ans);
    return 0;
}