ABC195 F Coprime Present

翌日のARCのAでも似たようなの見ましたね。

問題

読んで

解法

自明解として、の計算を回せば答えは出ます。

まあ流石にそれは間に合わないので高速化を考えます。選んだ数の集合すべてのペアが互いに素であるということは、素因数分解した際に素因数が同じであるものがないということを表します。しかし素因数分解をしたくても、最大の数がだったりするので、素因数分解は難しいでしょう。

とかいう変な制約がバチバチに怪しいのでこれを踏まえて考えてみます。

まず互いに素ということは、偶数同士は絶対に同じにできません。0以外の偶数は素因数に2を含むからです。そして偶数は一つ飛ばしで並んでいます。

同様に、3の倍数同士も絶対に同じにできません。3の倍数は二つ飛ばしで並んでいます。

そのようなことを考えていると、なので、たかだかまでの素因数しか考えなくて良さそうな気持ちになります。

証明してみます。

よりも大きい素数で、かつ一番小さい数はです。ある数の組が互いに素ということは、二つの数を素因数分解した際に、素因数が同じであるものがないということと同義です。

二つの数を素因数分解した際にが両方に出てくるということは、両者がの倍数であるということです。の倍数は72飛ばしで並んでいます。

しかしこの問題では選べる数の範囲が最大でも72個の連番になっています。つまり範囲の最初にの倍数があっても、次のの倍数は範囲外となってしまいます。

これより、より大きい素数で初めて割れる数は、与えられた入力の中では実質的な素数として扱っても差し支えはなさそうです。

よって、たかだかまでの素数で素因数分解してやればいいということがわかりました。

そしてまでの素数はちょうど個であるので、は十分間に合います。

あとはbitDPで解けるんですが、このbitDPは思いつかなかったな......。含んでいる素数でbit全探索を考えて壊れました。

その後含んでいる素数でbitDPを考えたんですが回らず、解説を見るとからの数を一つ一つ集合に加えていくかでbitDPということがわかって、それはそう～と叫ぶとACできました。うーんこの辺は純粋に経験の差だなあ。もっと詰めていきます。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    ll a, b; cin>>a>>b;

    const vector<ll> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

    auto prime_factor = [&](ll x) {
        int m = prime.size();
        ll tmp = 0;
        rep(i,m) {
            if (x%prime[i] == 0) {
                tmp |= (1<<i);
            }
        }
        return tmp;
    };

    ll ans = 0;
    ll n = prime.size()+1;
    vector<ll> dp(1<<n);
    dp[0] = 1;

    for (ll i = a; i <= b; ++i) {
        for (ll bit = 0; bit < (1<<n); ++bit) {
            if (dp[bit] == 0) continue;
            ll t = prime_factor(i);
            bool ok = true;
            rep(j,n) {
                if (bit & (1 << j) && t & (1 << j)) {
                    ok = false;
                }
            }
            if (!ok) continue;
            ll nxt = bit | t;
            dp[nxt] += dp[bit];
        }
    }

    rep(i,(1<<n)) ans += dp[i];
    cout << ans << '\n';

    return 0;
}