Coprime Present [パナソニックプログラミングコンテスト（AtCoder Beginner Contest 195） F]

https://atcoder.jp/contests/abc195/tasks/abc195_f

前提知識

• bitDP

解説

https://atcoder.jp/contests/abc195/submissions/20909698 多分初見だと何も手につかないような気がするが、色々な部分から解法を持ってくる。
bitDPが分からないと最終的な答えにたどり着かないので、知らない人はそちらを学習することをお勧めする。

互いに素

区間を扱うのはいいのだが、それよりも「互いに素」という部分をどうするかが問題となる。
例えば選択した数が互いに素であるかを判定するにはどうすればいいだろうか。
全ての組についてGCDを求めて1であるかを判定するという方法もあるが、使えそうにない。
逆に互いに素でない場合はGCDを取ると2とか4とかになる。
GCD基準で考えると、2は4を包含してないかとかとても面倒な話になってくる。
素数で考えることはできないか？

この辺でたぶんbreakthroughが必要になる。

"区間"ということを生かす

全ての組についてGCDを求めて1であるかを判定するという考え方を再考してみると、
全ての組について同じ倍数となる数が存在しないということになる。
そして、AとBが4の倍数であれば、自明にAとBは2の倍数ということになるので、素数倍数だけを考えればいい。

ここで"区間"であることを思い出してみよう。
今回の区間は最長で73の長さを持つ。
この時、ペアとして成立しうる倍数の最大値は72である。
72の倍数であれば、被ることがあり得るし、それより大きい倍数が被ることはない。
かつ、素数倍数だけを考えればいいので、区間について、72以下の素数の倍数が含まれるかどうかが判定できればいい。
なお、72以下の素数は20個なので、これは使えそうな条件だ！

bitDPへ

ここから、少し頑張るとbitDPに発展させることができる。
dp[i][lcm] := Aからi番目の数までを使って、使った数の素因数として使われたものの集合がlcmである場合の組み合わせ
lcmについては{2,3,5,7,11,...}みたいな集合に対して使ったかどうかを想定する。

前計算として
msk[i] := Aからi番目の数について、素因数として使われたものの集合
を計算しておこう。
すると、毎回の遷移でlcm & msk[i]が0でないなら、素因数が被っている、つまり、互いに素でなくなるので遷移はしない。
これを考慮してオーソドックスなbitDPをすれば答えが得られる。

ll A, B;
ll dp[74][1 << 20];
int msk[73];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> A >> B;

    auto ep = makePrimes(72);
    // cout << ep.size() << endl;     == 20

    for (ll x = A; x <= B; x++) rep(i, 0, 20) if (x % ep[i] == 0) msk[x - A] |= 1 << i;

    dp[0][0] = 1;
    for (ll x = A; x <= B; x++) rep(lcm, 0, 1 << 20) {
        if ((lcm & msk[x - A]) == 0) dp[x - A + 1][lcm | msk[x - A]] += dp[x - A][lcm];
        dp[x - A + 1][lcm] += dp[x - A][lcm];
    }

    ll ans = 0;
    rep(lcm, 0, 1 << 20) ans += dp[B - A + 1][lcm];
    cout << ans << endl;
}