E - 天下一演算
Editorial
/
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
あなたは天下一演算というゲームで遊んでいます。天下一演算は以下のように定義されます。
- 1 以上 10^5 以下の整数 M、N と、0 以上 M 未満の整数 N 個からなる配列 A が与えられる。
- 配列の全ての要素に 10 を掛ける操作を何回か行う。
- その後、配列のある 1 つの要素に 1 を足す操作を何回か行う。
- 全ての要素が M の倍数になるとクリアとなる。
例えば、M = 7、N = 4、A = \[0, 1, 2, 3\] のとき、全ての要素に 3 回 10 を掛けた後、2 番目の要素に 1 回 1 を足し、3 番目の要素に 2 回 1 を足し、4 番目の要素に 3 回 1 を足すと、A = \[0, 1001, 2002, 3003\] となり、合計 9 回の操作で全ての要素が M の倍数になります。
天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を求めてください。
入力
入力は以下の形式で標準入力から与えられる。
M N A_1 A_2 : A_N
- 1 行目には、2 つの整数 M (1 ≦ M ≦ 10^5)、N (1 ≦ N ≦ 10^5) が空白区切りで与えられる。
- 2 行目からの N 行に、配列 A のそれぞれの要素 A_i (0 ≦ A_i < M) が与えられる。
出力
天下一演算をできるだけ少ない回数の操作でクリアしたときの、合計の操作回数を出力せよ。出力の末尾に改行を入れること。
配点
この問題には部分点は設定されていない。正解した場合は、130 点が与えられる。
入力例1
7 4 0 1 2 3
出力例1
9
問題文中で説明したケースです。
入力例2
1001 1 1
出力例2
4
3 回 10 を掛けた後、1 回 1 を足すと、M の倍数になります。
入力例3
1 2 0 0
出力例3
0
はじめから M の倍数です。
入力例4
12345 5 12 34 56 78 90
出力例4
1884