No.368 LCM of K-products
タグ : / 解いたユーザー数 140
作問者 :
🍡yurahuna
/ テスター :
🐬hec
問題文
$N$ 個の正整数からなる数列 $A = \{a_1, a_2, \dots, a_N\}$ があります。
$A$ の添字が異なる $K$ 個の要素の積からなる集合を $B$ とします。
このとき、$B$ の全要素の最小公倍数を $10^9 + 7$ で割った余りを求めてください。
入力
$N$ $K$ $a_1$ $a_2$ ... $a_N$
1行目には数列 $A$ の要素数 $N (1 \leq N \leq 1000)$ および $K (1 \leq K \leq N )$ がスペース区切りの整数で与えられる。
2行目には数列 $A$ の要素 $a_i (1 \leq i \leq N, 1 \leq a_i \leq 10^9)$ がスペース区切りの整数で与えられる。
出力
答えを1行で出力し、改行してください。
サンプル
サンプル1
入力
3 2 2 3 5
出力
30
この例では $B = \{ a_1 \times a_2, a_1 \times a_3, a_2 \times a_3 \} = \{6, 10, 15\}$ となります。
$B$ の全要素の最小公倍数は30です。
サンプル2
入力
3 2 2 4 8
出力
32
$B = \{8, 16, 32\}$ です。
サンプル3
入力
4 3 2 2 2 2
出力
8
$B = \{ a_1 \times a_2 \times a_3, a_1 \times a_2 \times a_4, a_1 \times a_3 \times a_4, a_2 \times a_3 \times a_4 \} = \{8, 8, 8, 8\}$ です。
$B$ の作られ方に注意してください。
サンプル4
入力
3 1 2016 4 11
出力
22176
$K = 1$ なので、$B = \{ a_1, a_2, a_3 \} = \{2016, 4, 11\}$ です。
サンプル5
入力
10 7 832 223 29375 10 447239 999299573 5272 829829 6265 33
出力
738866291
$10^9 + 7$ で割った余りを出力してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。