/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 個の正整数 A_1,...,A_N が与えられます。
次の条件を満たすような正整数 B_1,...,B_N を考えます。
条件：1 \leq i < j \leq N を満たすどのような i,j についても A_i B_i = A_j B_j が成り立つ。
このような B_1,...,B_N における B_1 + ... + B_N の最小値を求めてください。
ただし、答えは非常に大きくなる可能性があるため、(10^9 +7) で割ったあまりを出力してください。
制約
- 1 \leq N \leq 10^4
- 1 \leq A_i \leq 10^6
- 入力中のすべての値は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 ... A_N
出力
条件を満たすような B_1,...,B_N における B_1 + ... + B_N の最小値を (10^9 +7) で割ったあまりを出力せよ。
入力例 1
3 2 3 4
出力例 1
13
B_1=6, B_2=4, B_3=3 とすると条件を満たします。
入力例 2
5 12 12 12 12 12
出力例 2
5
全ての B_i を 1 とすればよいです。
入力例 3
3 1000000 999999 999998
出力例 3
996989508
和を (10^9+7) で割った余りを出力してください。
Score : 500 points
Problem Statement
Given are N positive integers A_1,...,A_N.
Consider positive integers B_1, ..., B_N that satisfy the following condition.
Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.
Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.
Since the answer can be enormous, print the sum modulo (10^9 +7).
Constraints
- 1 \leq N \leq 10^4
- 1 \leq A_i \leq 10^6
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 ... A_N
Output
Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).
Sample Input 1
3 2 3 4
Sample Output 1
13
Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.
Sample Input 2
5 12 12 12 12 12
Sample Output 2
5
We can let all B_i be 1.
Sample Input 3
3 1000000 999999 999998
Sample Output 3
996989508
Print the sum modulo (10^9+7).