GCJ Qualification Round 2016 Problem C. Coin Jam
問題
Dashboard - Qualification Round 2016 - Google Code Jam
長さ N(N >= 2) の文字列 s が以下の条件を満たしていると嬉しい。
- s[0] = s[N-1] = '1'
- s の各文字列は '0' または '1'
- 文字列 s を基数 b (2 <= b <= 10) における数と見た時, どの基数を取ってきても合成数になっている
文字列の長さ N が与えられるので, 以上の条件を満たす s を J 個挙げよ。ただし, 各 s の各基数 b に対して, それが合成数であることを示すために, 「文字列 s を基数 b における数と見た時, それを割り切る数」もちゃんと書かないとダメ。
(あらかじめわかってる制約)
small: N=16, J=50
large: N=32, J=500
解法
s に立っている bit が奇数の場合は b=3, 5, 7, 9 では必ず偶数になって割り切れます。後は 2, 4, 6, 8 が問題ですが, これは 2, 3, ..., 100 以内で割り切れたら OK, とやると J の制約に間に合いました。
ただ一番かしこいのは 16bit ごとに分けて同じ bit を 2 つ並べると必ず合成数になる, ってやつですかね…
bool check(ll s, int d, int base) { ll rest = 0; while (s) { rest = (base*rest + (s%2)) % d; s /= 2; } return rest == 0; } bool ok(ll s) { vector<ll> divs; for (int base = 2; base <= 10; base++) { if (base%2 == 1) { divs.push_back(2); continue; } int d = 3; for (; d <= 100; d++) { if (check(s, d, base)) { divs.push_back(d); break; } } if (d > 100) return false; } string tmp; while (s) { tmp += (char)((s%2)+'0'); s /= 2; } cout << tmp << " "; for (int i = 0; i < 9; i++) { cout << divs[i] ; if (i < 9-1) cout << " "; } cout << endl; return true; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T, N, J; cin >> T; cin >> N >> J; int cnt = 0; cout << "Case #1:" << endl; for (ll s = (1ll<<(N-1)); s < (1ll<<N); s++) { if (cnt==J) break; if (s%2==0) continue; if (__builtin_popcountll(s)%2 == 1) continue; if (ok(s)) cnt++; } return 0; }