COLOCON 2018

COLOCON -Colopl programming contest 2018- - AtCoder

C - すぬけそだて――ごはん――

問題

$A$ 以上 $B$ 以下の整数の集合を $P$ とし、$P$ の部分集合を考える（空集合含む）
どの2つをとっても互いに素である部分集合の個数は？
$B - A \le 35$

例: A=6 B=9 なら、
    φ {6} {7} {8} {9} {6,7} {7,8} {7,9} {8,9} {7,8,9} の10通り

解法

制約より、数字は最大でも36個しかない。

各数について「自身を割り切る36未満の素数の集合」を計算する。36未満の素数は「2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31」。36以上の素数は、連続する36個の数字の中では共通して約数に持つ2数は現れないため、考慮しなくてよい。

ある数字の集合が“どの2つを取っても互いに素である”かどうかは、“各数字を割り切る素数の集合が互いに素である”ということである。

例
整数   割り切る素数の集合
638 → {2, 11, 29}
644 → {2, 23}
665 → {5, 7, 19}
638と644で"2"が重複しているため、{638, 644, 665} は条件を満たさない

これを全ての集合について確認したい･･･が、全探索しようと思うと $2^{36}$ となり、時間的に無理。

ここで、2の倍数、3の倍数はそれぞれ1つまでしか入れられないことを利用する。（他の素数の倍数にも同じことが言えるが、2と3は特に数が多いので）

A～Bの数字を、4つに分類する

(a) 2と3どちらの倍数でもない
(b) 2の倍数(not 3)
© 3の倍数(not 2)
(d) 6の倍数

以下の集合のうち、条件を満たす個数の合計が答えとなる。

(d)から1つ選ぶ + (a)の部分集合の1つ

# Pythonっぽい擬似コード

ans = 0
for n2 in ((b) または 1):
    for n3 in ((c) または 1):
        for {a1, a2, a3 ...} in (a)の全ての部分集合:
            if n2, n3, a1～ak が全て互いに素なら:
                ans += 1
for n6 in (d):
    for {a1, a2, a3 ...} in (a)の全ての部分集合:
        if n6, a1～ak が全て互いに素なら:
            ans += 1

ここで、(a)の全探索は繰り返し行うため、あらかじめ(a)の中だけで条件を満たすか判定を行い、「割り切る素数の集合」もまとめてしまうとよい。

(a): {35, 37, 49, 55}  （※本当は53とか間の数がもっとあるはずだが、説明のため省く）
(a)の部分集合  条件判定  割り切る素数の集合（合算）
φ                ○     {}
{35}              ○     {5, 7}
{37}              ○     {}
{49}              ○     {7}
{55}              ○     {5, 11}
{35, 49}          ×
{35, 37}          ○     {5, 7}
{35, 55}          ×
{37, 49}          ○     {7}
{37, 55}          ○     {5, 11}
{49, 55}          ○     {5, 7, 11}
{35, 37, 49}      ×
{35, 37, 55}      ×
{35, 49, 55}      ×
{37, 49, 55}      ○     {5, 7, 11}
{35, 37, 49, 55}  ×

→ {}:2個  {7}:2個  {5,7}:2個  {5,11}:2個  {5,7,11}:2個

この事前計算の結果を集合 $Di$, カウント $Ci$ とすると、先ほどの擬似コードは

ans = 0
for n2 in ((b) または 1):
    for n3 in ((c) または 1):
        for Di, Ci in 事前計算結果:
            if n2, n3, Di が全て互いに素なら:
                ans += Ci
for n6 in (d):
    for Di, Ci in 事前計算結果:
        if n6, Di が全て互いに素なら:
            ans += Ci

となり、ループ数を減らすことが出来る。

目次

COLOCON 2018

C - すぬけそだて――ごはん――

問題

解法