AtCoder Beginner Contest 152 E.Flatten

题目来源

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\le i<j\le N,A_i{B}_i=A_j{B}_j$ holds.
Find the minimum possible value of $B_1+...+B_N$for such$B_1,\dots ,B_N.$

Since the answer can be enormous, print the sum modulo $(10^9+7)$

Constraints

• $1\le N\le 10^4$
• $1\le A_i\le 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

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

自学了一下Markdown，终于能展示题面啦嘻嘻(●’◡’●)
这道题python过的，技巧就是内置的sum函数，否则会超时，吐槽一下python的强大，直接暴力：

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
n=int(input())
mod=1000000007
s=[int(i) for i in input().split()]
ans=1
for i in s:
    ans*=i//gcd(ans,i)
print(sum(ans//i for i in s)%mod)