Codeforces #450 Div2 D. Unusual Sequences

さすがに適当すぎたかな…。
http://codeforces.com/contest/900/problem/D

問題

正の整数列であるAのうち、GCDがXで和がYであるものは何通りあるか。

解法

YはXの倍数でないといけないのは自明。
あとはY/Xをいくつかの整数和にしたとき、GCDが1となるものを求めることを考えよう。

f(K) := 和がKとなる正の整数列のうちGCDが1となるものの数
とする。f(Y/X)が求めたい値である。
f(1)=1は自明なので、以降それ以外を考えよう。

まずGCDを無視してKの分け方を考える。
1をK個並べて、(K-1)個の隙間に仕切りを入れるか入れないかを考えるとこれは2^(K-1)通りであることがわかる。
そこからGCDが2以上のケースを引こう。
なお、GCDがdとなるケースの組み合わせは、Kがdの倍数であるときf(K/d)通りである。

まとめると、結局f(K)は2^(K-1)から、Kのの1以外の約数dに対しf(K/d)通りを順次引いていけばよく、メモ化再帰で解くことができる。

int X,Y;
ll mo=1000000007;
map<int,ll> memo;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(int X) {
	if(X==1) return 1;
	if(memo.count(X)) return memo[X];
	
	ll pat=modpow(2,X-1);
	
	for(int i=2;i*i<=X;i++) if(X%i==0) {
		pat-=hoge(X/i);
		if(X/i!=i) pat-=hoge(i);
	}
	pat--;
	
	return memo[X]=(pat%mo+mo)%mo;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y;
	if(Y%X) return _P("0\n");
	Y/=X;
	
	cout<<hoge(Y)<<endl;
	
	
}

まとめ

シンプルな問題設定でいいね。