Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 233 C 問題 Product

AtCoder ABC ABC233 C問題 300 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

次を満たすような整数の組 (j_1, \dots, j_N) の個数を求めよ.

  • i=1,2, \dots, N に対して, 1 \leq j_i \leq L_i
  • a_{1,j_1} \times \dots \times a_{N,j_N}=X

制約

  • N \geq 2
  • L_i \geq 2
  • L_1 \times \dots \times L_N \leq 10^5
  • 1 \leq X \leq 10^{18}

解法

L_1 \times \dots \times L_N \leq 10^5 なので, i=1,2, \dots, N に対して, 1 \leq j_i \leq L_i を満たすような (j_1, \dots, j_N) を全探索できる. よって, 深さ優先探索や, 直積集合を生成することにより, 実際に計算して a_{1,j_1} \times \dots \times a_{N,j_N}=X かどうかを判定して条件を満たす組の数を出力すれば良い.

なお, この問題は動的計画法でも解くことができる. {\rm DP}[i,x] を最初から i 個までみて積が x であるような組の数とする. このとき,

\displaystyle {\rm DP}[i,x]=\begin{cases} \begin{cases} 1 & (x=1) \\ 0 & (x \neq 1) \end{cases} & (i=0) \\ \displaystyle \sum_{\substack{1 \leq j \leq L_i \\ a_j | x }} {\rm DP}[i-1, x/a_j] & (i \geq 1) \end{cases}

である. 計算量について, そもそも X の約数ではないような x について考慮しなくてもよく, その工夫により 10^{18} 以下の正の整数で約数の個数は最大でも 103680 であり, L_i \geq 2, L_1 \times \dots \times L_N \leq 10^5 という制約から, N \leq 16 である. よって, このような動的計画法でも十分高速である (詳細は加筆するかもしれない).