yukicoder No.917 Make One With GCD 解説

問題

数列$ A_1,A_2,\ldots,A_Nの部分列で「全ての要素の最大公約数が$ 1である(★)」ものの数を求めよ。

制約

$ 1 \leq N \leq 50

$ 1 \leq A_i \leq 10^8

解法

$ 10^8 < 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23だから$ A_mの素因数は高々8個である。$ U:=(A_m,\ldots,A_N)の部分列のうち、$ A_mを含むものであって、★でないものの数（◆）を数えたい。$ A_m=\prod p_i^{e_i}について、$ S_i:=「全ての要素の最大公約数が$ p_iで割れる$ Uの部分数列の集合」とする。すると◆は包除原理から

$ \#\bigcup_i S_i = \sum_{J} (-1)^{|J|+1} \#\bigcap_{j \in J} S_j

と表せる。$ \#\bigcap_{j \in J} S_j = 2^{\# \{A_k : m < k \leq N,\forall j \in J, p_j \mid A_k\}}であるから$ \#\bigcup_i S_iは$ O(2^d\times N)で求まる($ dは$ A_iの約数の数。$ d\leq 8)。従って★は$ O(2^d \times N^2)で求まる。