yukicoder No.917 - No.917 Make One With GCD

• 問題
• AC

$A$に登場する素因数を（重複なしで）すべて集めて$p_1, p_2, ..., p_k$とする時、これらのどれも公約数とならないような部分列の数を求めればよい。包除を考えれば計算できそう。

正整数$x$が与えられたとする。$A_1, A_2, ..., A_N$のうち$x$で割り切れるものの総数を$f(x)$とするとき、$x$が公約数であるような部分列の数は（空の部分列を除いて）$2^{f(x)}-1$である。したがって、求める数は包除原理に従って

$(2^{f(1)}-1) \\ \ - (2^{f(p_1)}-1) - (2^{f(p_2)}-1) - ... - (2^{f(p_k)}-1) \\ \ + (2^{f(p_1p_2)}-1) + (2^{f(p_1p_3)}-1) + ... + (2^{f(p_{k-1}p_k)}-1) \\ \ - ... \ + (-1)^k(2^{f(p_1p_2...p_k)}-1)$

のようになる。素数の数が奇数なら引いて偶数なら足せばよい。ただし、登場する素数の総数$k$はだいぶ大きくなることがあるので、上の式の$2^k$項全部を計算していては間に合わない。$10^8$を超えるものを枝刈りすれば間に合う。

---

これ、計算量がわからない。正整数$A$と素数列のprefix$\{2, 3, 5, 7, ..., p_k\}$が与えられたとき、prefixの部分集合で総積が$A$を超えないようなものが何通りあるか？ という問題に帰着しそうだけど……

---

50
97132843 98363449 89581363 82864427 98796221 99147481 74352463 99477713 93924871 65541251 99070949 98476523 99270979 99661321 99880747 98045347 99838183 98904791 99582083 89757337 99752171 98440403 99331283 98037839 99472123 98862697 99813167 99238807 99743993 99408347 99727399 97821397 99594503 98248609 98207933 99677881 90900499 81927497 68034287 54143561 90426598 35950241 73138803 82613935 68388971 92946349 33984931 12780049 64097801 1062347

最悪っぽいケースを作ってみたらだいぶ時間が怪しかった。