問題一覧 > 通常問題

No.1330 Multiply or Divide

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 85
作問者 : penguinmanpenguinman / テスター : nok0nok0
18 ProblemId : 5191 / 出題時の順位表
問題文最終更新日: 2021-01-17 18:21:21

問題文

素数 $P$ と、長さ $N$ の数列 $A$ があります。はじめ $1$ で初期化されている変数 $x$ に対して、$x$ が $M$ 以下である限り以下の操作を繰り返します。

  • もし $x$ が $P$ で割り切れるなら、$x$ を $P$ で割る。
  • そうでないとき、 $1≤i≤N$ を満たす整数 $i$ を選び、$x$ に $A_i$ を掛ける。

操作回数が最小になるように操作をしたとき、合計で何回操作をすることになりますか?

ただし、どのように要素を選んでも操作が無限に繰り返される場合は $-1$ を出力してください。


入力

$N\ M\ P$
$A_1\ A_2\ ...\ A_N$
  • $1≤N≤2×10^5$
  • $1≤M,P≤10^9$
  • $1≤A_i≤10^9$
  • $P$ は素数
  • 入力は全て整数

出力

操作が有限回で終わる場合操作回数の最小値を、終わらない場合 $-1$ を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3 5 2
4 2 3
出力
2

$3$ を選び続けるのが最善です。

サンプル2
入力
3 400 2
2 256 128
出力
-1

どのように選んでも、 $x$ は $M$ を超えません。

サンプル3
入力
8 29019 59
59 13021 392 192 392 12 293 40
出力
2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。