GCJ Qualification Round 2016 C. Coin Jam

01 で構成された長さ N の文字列を 2～10 進法で書かれた値と読み替えたとき、どの進法でも合成数になるようなものを J 個見つけよ。

また見つけた各文字列に対し、2～10 進法での非自明な約数をそれぞれ一つずつ示せ。

N 進法で表された数の偶数桁目の総和と奇数桁目の総和が等しいとき N+1 の倍数になるという性質を使う。

N 進法で表された数を mod N+1 すれば分かる。 $$ a_0+a_1 N+a_2 N^2+a_3N^3+\cdots=a_0-a_1+a_2-a_3+\cdots $$

これを使えば 110011 は 2 進法では 3 の倍数だと分かるし、3 進法では 4 の倍数だと分かるし、10 進法では 11 の倍数だと分かる。

よって偶数桁目にある 1 の数と奇数桁目にある 1 の数が等しいものを 500 個持ってくればいい。500 個ぐらいなら愚直列挙で見つかる。

N が小さい時に備えて small 解法も書いてたのに N は 16,32 で固定で悲しい。