ABC195Fの解答

F - Coprime Present (2068)

問題文

あなたは A 以上 B 以下の整数が書かれたカードを各 1 枚、合計 A 以上 B 以下の整数が書かれたカードを各 1 枚、計 B−A+1 枚持っています。 この中から何枚かを選んで (0枚でもよい) ペットのすぬけ君にプレゼントしようと考えています。
すぬけ君は、プレゼントされたカードたちについて、どの相異なる 2 枚に書かれた数も互いに素であるときに喜び、そうでないとき悲しみます。
すぬけ君が喜ぶようなカードの組合せは何通りありますか？

制約

1 ≤ A ≤ B ≤ 10^18
B − A ≤ 72
入力は全て整数

考察

すぬけくんが喜ぶ条件は選んだカードが「互いに素」であるときです。これは、選んだカードのなかで 1 以外の同じ約数が登場しない場合ということができます。ということで、まずは約数について考えて問題文を言い換えます。

制約を見ますと

1 ≤ A ≤ B ≤ 10^18

ですので、全てを素因数分解するのは無理があります。エラトステネスの篩みたいな強いアルゴリズムでも時間が相当時間がかかります。ただし、次の制約は

B − A ≤ 72

です。ですので、該当する数字は最大で73個の連続した自然数となります。この条件から考えなければならない約数（素数）を絞ります。

本問題で考慮すべきなのは先に書いた通り

選んだカードの中で同じ約数が存在しないかどうか

です。この「同じ約数」になり得るものというのはある程度絞ることが可能です。

例えば、2を約数に持つものは

1 2 3 4 5 6 7 8 ...

で2個離れて出現します（１つおきというのでしょうか）。同様に3を約数に持つものは

1 2 3 4 5 6 7 8 9 ...

で、3個離れて出現します（該当数字を太字にしてますが見にくいかもしれません）。このように、ある約数 d を持つ数字は d 個離れた場所に出現します。言いかえますと、 d 未満の距離にある数字には d の約数は出現しないということです。今回、考える数字の区間は73です。73の約数を持つ数字は73個離れないと出現しませんので、本問題の区間内において73以上の約数は2個以上出現することがありません。また、72は2回以上出現する可能性はありますが、これは2*2*2*3*3ですので、2と3を約数に持つ数字と見なすことができます（本問題では約数の個数ではなく、互いに素であることが重要）。

したがって、問題文は次のように言い換えられます。

最大73個の連続する数字から、71以下の素数のうち同じものを持たないように選ぶ選び方は何通りありますか？

約数に関しては以上です。次にこれを数え上げる方法を考えます。

本問題はbitDPを用いることで解くことが可能です。構成は

dp[ i ][ s ]:
i 番目の数字まで考え、
選択した数字に含まれる素因数が s である
場合の組み合わせの数

です。まず、sの部分について考えます。2回以上出現するのは71以下であり、その素数は次の20個しかありません。

{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}

ですので、sは2進数表現で20桁用意して、各桁が1であればその素数が存在する、0であれば存在しない、表現できます。これがbitDPたる所以です。

素因数 2 5 11 13 をもつ
  13, 11, 7, 5, 3, 2
s =...110101 = 53

s は最大で2^20 = 1048576 、数字は最大73個ですので十分扱いきれます。

次に遷移を考えます。i 番目の数字を考えたときに 

「i 番目の数字を選択する」
「選択しない」

の2つ遷移が起こります。ただし、問題の条件として同じ素因数を持ってはいけません。そのため、「選択する」場合には条件を次の条件をクリアしなければなりません。

i 番目の数字が71以下の素数のうちどれを約数に持つかを計算する。これをs_i とする。現在の素数集合 s に s_iがひとつも含まれていない。

上記を満たした場合にのみ遷移可能です。

例を一つ見ます。2 3 4 5 6 としましょう。

2の約数は 2 だけです。ですので、s_0 = ...001ですね。ですので、s の1桁目が 0 のとき遷移が可能です(s = ...000, ...110など)。逆に 1 が立っていたら遷移できません(s = ...001, ...111など)。遷移は次のようになります。

例：dp[1][...001] += dp[0][...000]

3と5は2の場合と同様です（s_1 = ...010, s_3=...100 ）。4の場合にはその約数は2*2となりますが、約数の個数は関係ありませんので、2と同様に扱えます(s_2=...001)。

6は2*3となりますのでs_4 = ...011です。そのため s の1桁目と2桁目がともに 0 の場合にのみ遷移可能です。

例：dp[5][...011] += dp[4][...000]

以上が「 i 番目の数字を選択」した場合です。

「選択しない」場合には s に含まれる約数が増えることはありませんので気にせず遷移しちゃいましょう。

例：dp[5][...101] += dp[4][...101]

遷移をまとめると次の式になります。

選択する：dp[i+1][s|s_i] += dp[i][s]
選択しない：dp[i+1][s] += dp[i][s]
sにs_iが含まれていない場合「選択する」が可能

説明は以上になります。実装しましょう。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71};
const int n = 20;
const ll bn = 1 << n;
ll dp[75][bn];

int main()
{
   ll a,b;
   cin >> a >> b;
   dp[0][0] = 1;
   int idx = 0;
   for(ll i = a; i<= b; ++i)
   {
       ll ai = i;
       ll si = 0;
       //71以下の素数のうちどれを持つか計算する
       rep(j,n) if(ai%p[j]==0) si |= (1<<j);//(今回si+=(1<<j)と同じ)
       rep(s,bn)
       {
           //aiを選択しない
           dp[idx+1][s] += dp[idx][s];
           //aiを選択する（sにaiの素因数がない場合に可能）
           if((s&si) == 0) dp[idx+1][s|si] += dp[idx][s];
       }
       ++idx;
   }
   ll ans = 0;
   //全部の数字を見終わったあとにその組み合わせはいくつあるかを計算する
   rep(s,bn) ans += dp[idx][s];
   cout << ans << endl;
   return 0;
}

あとがき

制約から問題文を言い換える点が本問題の本質であったと思います。それさえこなしてしまえば、比較的シンプルなbitDPで答えが求まります。本問題のdiffは高いですがbitDPの練習に良いと思います。あとはABC180Eの巡回セールスマン問題とかでしょうか。

実装に関してですが、選択するの約数が含まれてるかどうかの判定で

if((s&si) == 0)

としています。これを

if(s&si == 0)

とすると、演算子の優先度により

if(s & (si==0))

と解釈されてしまいますのでお気をつけを。私はこれでバグらせました。bitごとのor演算 「 | 」とand演算「 & 」、bitシフト「 << 」はbitDP、bit全探索なんかでよく使いますので、調べなくても使えるようになっておくと良いかもしれませんね。

これにてABC195(パナソニックプログラミングコンテスト)の解説はおしまいです。B問題で悩んだり、D問題は貪欲で解けたりと、いつもと少し違って私的にはとっても楽しいコンテストでした。今週末にもABCがありますので、参加、感想、解答までを頑張ってやりたいなと思います。

長くなりましたが、ここまで読んでいただきありがとうございました。本記事が少しでも皆様のお役に立てたら嬉しい限りです。