Codeforces839D Winter is here(수론: 배제 원리)

D. Winter is here
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Winter is here at the North and the White Walkers are close. John Snow has an army consisting of n soldiers. While the rest of the world is fighting for the Iron Throne, he is going to get ready for the attack of the White Walkers.
He has created a method to know how strong his army is. Let the i-th soldier’s strength be ai. For some k he calls i1, i2, ..., ik a clan ifi1 i2 i3 ik and gcd(ai1, ai2, ..., aik) > 1 . He calls the strength of that clan k·gcd(ai1, ai2, ..., aik). Then he defines the strength of his army by the sum of strengths of all possible clans.
Your task is to find the strength of his army. As the number may be very large, you have to print it modulo 1000000007 (109 + 7).
Greatest common divisor (gcd) of a sequence of integers is the maximum possible integer so that each element of the sequence is divisible by it.
Input
The first line contains integer n (1 ≤ n ≤ 200000) — the size of the army.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 1000000) — denoting the strengths of his soldiers.
Output
Print one integer — the strength of John Snow's army modulo 1000000007 (109 + 7).
Examples
input

3
3 3 1

output

12

input

4
2 3 4 6

output

39

Note
In the first sample the clans are {1}, {2}, {1, 2} so the answer will be 1·3 + 1·3 + 2·3 = 12
제목:
그 중에서 GCD가 1이 아닌 수의 서열 길이에 대응하는 GCD의 합을 곱하기 위해 몇 가지 수를 제시한다.emmmm..주로 예를 보고 이해한다.
아이디어:
먼저 n개의 수가 있다는 것을 알아야 한다. 그러면 이 n개의 조합 길이가 0이 아닌 조합은 모두 n*(2^(n-1)종이 있다. 이 규칙을 알고 나서 우리는 F(x)가 이 공식의 반환값이라고 가정한다.GCD가 4일 경우 2에서 4를 더 많이 기록하는 경우도 고려해야 한다.이때 용척 원리를 따르면, 이때 2의 수량은 F(2)-F(4)-F(8)...F(2*n), 즉 어떤 수의 상황 수와 F(x)에서 x배수를 뺀 F다.이 법칙이 있으면 하기 쉽다.
코드:

#include
using namespace std;
const int  MAX_N = 1e6 + 9;
const int MOD = 1e9+7;
long long vec[MAX_N];
long long sum[MAX_N];
long long my_pow(long long x,int k)
{
    long long res = 1;
    while(k>0)//    while(k)      k=0    break， k<0      break。！
    {
        k--;
        res *= x;
        res %= MOD;//emmm。  MOD         
    }
    return res;
}
int main()
{
    int N,M,T;
    while(~scanf("%d",&N))
    {
        memset(vec,0,sizeof(vec));
        memset(sum,0,sizeof(sum));
        int maxn = -1;
        for(int i=0; i=2; i--)
        {
            //if(vec[i]) 
            //         ，        GCD 4 8     vec[2]
            //  0，    GCD 2        0
            long long tot = 0;
            for(int j=i; j<=maxn; j+=i)
            {
                sum[i] -= sum[j];
                tot += vec[j];
            }
            sum[i] += (tot*my_pow(2,tot-1)+ MOD) %MOD; //   MOD，  sum         
            ans += (i*sum[i])%MOD;
            ans = (ans+MOD)%MOD;
        }
        cout<