kmjp's blog

競技プログラミング参加記です

Google Code Jam 2016 Qualification Round : C. Coin Jam

割とすんなり。
https://code.google.com/codejam/contest/6254486/dashboard#s=p2

問題

1,0で構成されたN桁の数を考える。
この数を2~10進数と見なしたとき、それぞれが合成数となるようにしたい。
そのような数の例をJ個示し、それぞれ2~10進数と見なしたときの約数を1つずつ挙げよ。

解法

N桁の数が何進数だろうと、途中繰り下がりが生じず割り切れる約数が作れるならその数は割り切れる。
例えば1001100110011001は何進数でも1001で割り切れる。

このように、Nの約数dに対し、d桁の01で構成した数をN/d個連結すれば題意を満たせる。
あとはそのようなd桁の01のパターンを列挙していこう。
10011001と1001のように、実質N桁繰り返すと同じ値になるものを重複カウントしないように注意。

set<ll> did;

ll base(int mask,int b) {
	ll v=0;
	while(mask) {
		v=v*b+(mask&1);
		mask>>=1;
	}
	return v;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int N,J;
	cin>>N>>J;
	
	_P("Case #%d:\n",_loop);
	did.clear();
	for(i=2;i<=N&&J;i++) if(N%i==0) {
		for(int mask=0;J&&mask<1<<(i-2);mask++) {
			ll tmask=(1LL<<(i-1)) | 1 | (mask<<1);
			ll dmask=0;
			
			FOR(x,N/i) dmask=(dmask<<i) | tmask;
			if(did.count(dmask)) continue;
			did.insert(dmask);
			J--;
			
			FOR(x,N) _P("%d",(dmask>>x)&1);
			for(x=2;x<=10;x++) _P(" %lld",base(tmask,x));
			_P("\n");
		}
	}
}

まとめ

(N+1)で割った余りを考える方法もあったようだけど、こっちの方がわかりやすくないかな…。