配点 : 500 点
問題文
N 個の正整数 A1,...,AN が与えられます。
次の条件を満たすような正整数 B1,...,BN を考えます。
条件:1≤i<j≤N を満たすどのような i,j についても AiBi=AjBj が成り立つ。
このような B1,...,BN における B1+...+BN の最小値を求めてください。
ただし、答えは非常に大きくなる可能性があるため、(109+7) で割ったあまりを出力してください。
制約
- 1≤N≤104
- 1≤Ai≤106
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A1 ... AN
出力
条件を満たすような B1,...,BN における B1+...+BN の最小値を (109+7) で割ったあまりを出力せよ。
3
2 3 4
13
B1=6, B2=4, B3=3 とすると条件を満たします。
5
12 12 12 12 12
5
全ての Bi を 1 とすればよいです。
3
1000000 999999 999998
996989508
和を (109+7) で割った余りを出力してください。