mayoko’s diary

プロコンとかいろいろ。

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;
}