[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)...