Codeforces 839D Winter is here 组合数公式/容斥

C(n,1)+2*C(n,2)+3*C(n,3)+……+n*C(n,n)= ((1+x)^n)求导,x=1

{4,8}中算到2的部分可以在4的部分减掉，也就是从大到小算，去掉自身倍数的贡献

#include<bits/stdc++.h>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
#include<iostream>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<iomanip>
using namespace std;
#define ll long long
#define pb push_back
#define FOR(a) for(int i=1;i<=a;i++)
const int inf=0x3f3f3f3f;
const int maxn=1e6+9; 
const int mod=1e9+7;

int po[maxn];
int dp[maxn];
int cnt[maxn];
int f[maxn];

int main(){
	int n;scanf("%d",&n);
	po[0]=1;
	for(int i=1;i<=n;i++)po[i]=2*po[i-1]%mod;
	int c;FOR(n)scanf("%d",&c),cnt[c]++;
	int ans=0;
	int x;
	for(int i=maxn-1;i>1;i--){
		x=0;
		for(int j=i;j<=maxn;j+=i)x+=cnt[j];
		if(x){
			f[i]=1ll*x*po[x-1]%mod;
			for(int j=i+i;j<maxn;j+=i)f[i]=(f[i]-f[j]+mod)%mod;
			ans=(1ll*f[i]*i+ans)%mod;
		}
	}	
	printf("%d
",ans);
}