AtCoder Beginner Contest 215 D 問題 Coprime 2 の解説
はじめに
この記事では AtCoder Beginner Contest 215 D 問題 Coprime 2 を解く、計算量が悪いが AC する解法について書きます。
計算量の良い解法については公式解説を参照してください。
問題
長さ $N$ の正整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。
$M $ が与えられるので、$A$ のすべての要素 $A_i$ について $\gcd(A_i, k) = 1$ かどうか、を $k = 1, 2, \dots, M $ に対して判定してください。
制約: $ 1 \le N, M, A_i \le 10^5 $
解法
素因数分解を考えると「$\gcd(x, k) = 1$」と「$x$ のすべての素因数 $p$ について $\gcd(p, k) = 1$」が同値ですから、$A$ の代わりに $A_i$ の素因数を並べた列を考えても答えは同じです。これを $B$ としましょう。たとえば次のようになります。
- $ A = (\textcolor{#BA8066}{3}, \textcolor{#BAA966}{1}, \textcolor{#A1BA66}{9}, \textcolor{#66BA80}{5}, \textcolor{#66A1BA}{6}, \textcolor{#6677BA}{2}, \textcolor{#8066BA}{4}, \textcolor{#A966BA}{7}, \textcolor{#BA66A1}{8})$
- $ B = (\textcolor{#BA8066}{3}, \textcolor{#BAA966}{1}, \textcolor{#A1BA66}{3}, \textcolor{#A1BA66}{3}, \textcolor{#66BA80}{5}, \textcolor{#66A1BA}{2}, \textcolor{#66A1BA}{3}, \textcolor{#6677BA}{2}, \textcolor{#8066BA}{2}, \textcolor{#8066BA}{2}, \textcolor{#A966BA}{7}, \textcolor{#BA66A1}{2}, \textcolor{#BA66A1}{2}, \textcolor{#BA66A1}{2})$
さらに、明らかに、$B$ の重複する要素は無視できるので $B$ の長さはたかだか $10^5$ 以下の素数の個数と考えてよいです。具体的には 9592 です。
$k = 1, 2, \dots, M $ に対し「$B$ のすべての要素 $B_i$ について $\gcd(B_i, k) = 1$ かどうか」を考えます。いま $B_i$ は素数なので $\gcd(B_i, k) = 1 \Leftrightarrow B_i \nmid k$ です ($B_i \nmid k$ は、$B_i$ が $k$ を割り切らない、の意味です)。
計算量を見積もりましょう。
- 前半の $A$ から $B$ を求めるパートは、素因数分解を $N$ 回するため $O(N \sqrt{\max A})$ 時間
- 後半は各 $k$ に対し $B$ の要素を全部見ることになってもループ回数が $9592M \le 10^9$
したがって速い言語なら実行時間制限の 2 秒に間に合って AC できます。提出例: PyPy3 880ms
