[Codeforces] 839D. Winter is here
題目連結: http://codeforces.com/problemset/problem/839/D 超級無敵久沒寫blog了，記錄一下這題好了，我過然數學還是不太好QQ 首先我們可能會想要對每個gcd都計算答案，那這時候我們可能會想知道有可能對這個gcd有貢獻的人會有誰，所以不妨先計算好有多少個數字含有因數$i$。那接著我們就直接計算總長度，對於每個因數$i$計算$\sum_{j=0}^{cnt[i]} j\cdot \binom{cnt[i]}{j}$但是這樣會重複計算到太多人，所以要扣掉他的2倍、3倍....的答案，而要算答案的時候則再乘上$i$即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; const int C = 1000000 + 5; const int MOD = 1000000007; int arr[N], cnt[C]; lld ans[C], two[N]; int main(int argc, char* argv[]){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; two[0] = 1; for(int i=1;i<n;i++) two[i] = two[i-1]*2 % MOD; for(int i=0;i<n;i++){ cin>>arr[i]; cnt[arr[i]]++; } for(int i=1;i<=C;i++) for(int j=2;j*i<=C;j++){ cnt[i] += cnt[i*j]; } lld ret = 0; for(int i=C;i>=2;i--){ if(cnt[i]==0) continue; ans[i] = cnt[i] * two[cnt[i]-1] % MOD; for(int j=2;j*i<=C;j++) ans[i] = (ans[i]-ans[j*i]+MOD)%MOD; ret = (ret + i*ans[i]%MOD) % M