要素を1つ削除 2
整数が
n 個並んだリストがあります。このうち1つの整数を削除して、残りの数の積を m で割った余りが p になるようにするのが目的です。より正確には、削除する要素のインデックスを r としたとき、となるように削除する要素を選ぶ必要があります。もし、そのような要素があればその番号を出力し、存在しなければ
Impossible と出力してください。入力
最初の行には、3つの整数
n (1 ≤ n ≤ ), m (1 ≤ m ≤ ), p (0 ≤ s < m) が与えられます。2行目には、
n 個の整数 ( ≤ ≤ ) がスペース区切りで入力されます。出力
条件をみたす要素が存在しない場合は
Impossible と出力します。そうでなければ、そのような要素の最小のインデックスを出力してください。インデックスは1から始まります。例
入力 | 出力 |
3 8 5
5 0 9 | 2 |
3 8 5
5 10 7 | Impossible |
解説
- 5 * 9 = 45 ⇒ 45 mod 8 = 5 となるので、位置が 2 の 0 を削除すると残りの積を 8 で割った余りが 5 になります。
- どの要素を削除しても、残りの積を 8 で割った余りが 5 になるようにはできません。
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB