Codeforces #428 Div2 D. Winter is here

色々Wikipedia頼りに進んでたら全完で割と良い順位に。
http://codeforces.com/contest/839/problem/D

問題

N要素の整数列Aが与えられる。
Aの部分列BのGCDが2以上の時、|B|*GCD(B)のスコアが得られるとする。
Aの全部分列のうち、上記スコアの総和を求めよ。

解法

包除原理の要領で解く。
まず、A中にaの倍数が単純にf(a)個あったときを考える。
f(a)個中k個の要素の選び方を考えると、これらによるスコアの総和はとなる。
最後の総和の部分の式変形はWikipedia等に掲載されている。
二項係数 - Wikipedia

aの係数の部分を考える。
実際はaの倍数がf(a)個あったとして、その部分集合のうちGCDがaより大きなものがあるかもしれないので、それを取り除こう。

としてg(a)を大きな順を求め、g(a)*aの総和を求めればよい。

int N;
ll A[202020];
ll mo=1000000007;

ll num[1010100];
ll p[1010100];
ll p2[1010100];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		for(x=1;x*x<=A[i];x++) if(A[i]%x==0) {
			num[x]++;
			if(x*x!=A[i]) num[A[i]/x]++;
		}
	}
	
	p2[0]=1;
	for(i=1;i<=1000000;i++) p2[i]=p2[i-1]*2%mo;
	
	ll tot=0;
	for(i=1000000;i>=2;i--) if(num[i]) {
		p[i]=num[i]*p2[num[i]-1]%mo;
		for(j=i*2;j<=1000000;j+=i) p[i]-=p[j];
		p[i]=(p[i]%mo+mo)%mo;
		(tot+=p[i]*i)%=mo;
	}
	cout<<tot<<endl;
	
	
}

まとめ

TLEがかなり怖かった。