問題一覧 > 通常問題

No.1330 Multiply or Divide

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 121
作問者 : penguinman / テスター : nok0
お気に入りにしたユーザー ProblemId : 5191 / 自分の提出
問題文最終更新日: 2021-01-17 18:21:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 277 (順位表) の他の問題:

Problem Statement

There are a prime $P$ and a sequence $A$ of length $N$. For a variable $x$, initially set to $1$, the following operation is repeated as long as $x$ is at most $M$.

  • If $x$ is divisible by $P$, divide $x$ by $P$.
  • Otherwise, choose an integer $i$ satisfying $1≤i≤N$ and multiply $x$ by $A_i$.

When the operations are performed so that their number is minimized, how many operations are performed in total?

However, if the operations repeat infinitely no matter how the elements are chosen, print $-1$.


Input

$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$ is prime
  • All inputs are integers

Output

If the operations end after a finite number of times, print the minimum number of operations; otherwise, print $-1$.
Print a newline at the end.

Sample

Sample 1
Input
3 5 2
4 2 3
Output
2

It is optimal to keep choosing $3$.

Sample 2
Input
3 400 2
2 256 128
Output
-1

No matter how you choose, $x$ does not exceed $M$.

Sample 3
Input
8 29019 59
59 13021 392 192 392 12 293 40
Output
2

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