例: 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つに分類する
以下の集合のうち、条件を満たす個数の合計が答えとなる。
計算量も、(b)の要素数(たかだか12個) * ©の要素数(たかだか6個) * (a)の全探索(たかだか2^12個)となり、間に合う。
# 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
となり、ループ数を減らすことが出来る。