はまやんはまやんはまやん

hamayanhamayan's blog

すぬけそだて――ごはん―― [COLOCON -Colopl programming contest 2018- C]

https://colopl2018-qual.contest.atcoder.jp/tasks/colopl2018_qual_c

解法

https://colopl2018-qual.contest.atcoder.jp/submissions/1844499

「B-A≦35」という制約と「400点」ということから何かしら全探索をするのだろうと推測する。
連続する数に対して互いに素ということを考えると、[A,B]の中で偶数の数は最大1つしか選べないことが分かる。
しかも、35という数は半分全列挙的な雰囲気が出ているので、奇数の数をどう選ぶかを全探索する。
 
奇数の数を選ぶか選ばないかはビットをつかったループでやるといい。
具体的には「msk := 下位iビット目が1ならばi番目の奇数は選ぶ」というのを回していく。
偶数を選択をする前に、選ばれた奇数だけで全ての組が互いに素であるかを確認しよう。
こうすることで、選んだ偶数を入れても互いに素になるかは、奇数と偶数のチェックだけで済む。
あとは、条件をみたす個数を数え上げる。

ll A, B;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;
 
    vector<ll> v[2];
    for (ll x = A; x <= B; x++) v[x % 2].push_back(x);
 
    int n = v[1].size(); int m = v[0].size();
    int ans = 0;
    rep(msk, 0, 1 << n) {
        vector<ll> x;
        rep(i, 0, n) if (msk & (1 << i)) x.push_back(v[1][i]);
        int ok = 1;
        int nm = x.size();
        rep(i, 0, nm) rep(j, i + 1, nm) if (gcd(x[i], x[j]) != 1) ok = 0;
        if (ok) ans++;
        else continue;
 
        rep(mm, 0, m) {
            int ok = 1;
            rep(i, 0, nm) if (gcd(x[i], v[0][mm]) != 1) ok = 0;
            if (ok) ans++;
        }
    }
    cout << ans << endl;
}