Problem:


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).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9+7)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            a_fac_dic[f[0]] = f[1]
        al_facs.append(a_fac_dic)

    ans = 0
    for al_f in al_facs:
        curr_val = 1
        for prime, cnt in lcm_dic.items():
            if prime in al_f:
                curr_val *= pow_k(prime,(cnt-al_f[prime]))
                curr_val%=MOD
            else:
                curr_val *= pow_k(prime,cnt)
                curr_val%=MOD
        ans += curr_val
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9+7)
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            a_fac_dic[f[0]] = f[1]
        al_facs.append(a_fac_dic)

    # lcm = 1
    # for prim, cnt in lcm_dic.items():
    #     lcm *= (prim**cnt)
    # # print(lcm)

    # ans = 0
    # for a in al:
    #     ans += lcm//a
    #     ans%=(10**9+7)
    # print(ans)

    ans = 0
    for al_f in al_facs:
        curr_val = 1
        for prime, cnt in lcm_dic.items():
            if prime in al_f:
                curr_val *= (prime**(cnt-al_f[prime]))
                curr_val%=MOD
            else:
                curr_val *= (prime**cnt)
                curr_val%=MOD
        ans += curr_val
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    al_facs = []
    for a in al:
        fac = factorization(a)
        a_fac_dic = {}
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            a_fac_dic[f[0]] = f[1]
        al_facs.append(a_fac_dic)

    # lcm = 1
    # for prim, cnt in lcm_dic.items():
    #     lcm *= (prim**cnt)
    # # print(lcm)

    # ans = 0
    # for a in al:
    #     ans += lcm//a
    #     ans%=(10**9+7)
    # print(ans)

    ans = 0
    for al_f in al_facs:
        curr_val = 1
        for prime, cnt in lcm_dic.items():
            if prime in al_f:
                curr_val *= (prime**(cnt-al_f[prime]))
            else:
                curr_val *= (prime**cnt)
        ans += curr_val
        ans %= (10**9+7)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = {}
    for a in al:
        fac = factorization(a)
        for f in fac:
            lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
    lcm = 1
    for prim, cnt in lcm_dic.items():
        lcm *= (prim**cnt)
    # print(lcm)

    ans = 0
    for a in al:
        ans += lcm//a
        ans%=(10**9+7)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  # 最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): # 素因数分解の昇順リスト, {2:p,3:q,5:r,...}
        self.fact_dict=dict()
        while x!=1:
            p=self.f[x]
            self.fact_dict[p]=self.fact_dict.get(p,0)+1
            x//=self.f[x]
        return self.fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    p_a_lis=[]
    Prime=Sieve(max(A))
    for a in A:
        p_a_lis.append(Prime.prime_fact(a))
        for key in p_a_lis[-1]:
            if not p_lis.get(key,False) or p_lis[key]<p_a_lis[-1][key]:
                p_lis[key]=p_a_lis[-1][key]
    ans=0
    for i,a in enumerate(A):
        b=1
        for key in p_lis:
            b*=(key**(p_lis[key]-p_a_lis[i].get(key,0)))%mod
        ans=(ans+b)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def prime_fact(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    p_a_lis=[]
    for a in A:
        p_a_lis.append(prime_fact(a))
        for key in p_a_lis[-1]:
            if not p_lis.get(key,False) or p_lis[key]<p_a_lis[-1][key]:
                p_lis[key]=p_a_lis[-1][key]
    ans=0
    for i,a in enumerate(A):
        b=1
        for key in p_lis:
            b=(b*key**(p_lis[key]-p_a_lis[i].get(key,0)))%mod
        ans=(ans+b)%mod
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def prime_fact(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    p_a_lis=[]
    for a in A:
        p_a_lis.append(prime_fact(a))
        for key in p_a_lis[-1]:
            if not p_lis.get(key,False) or p_lis[key]<p_a_lis[-1][key]:
                p_lis[key]=p_a_lis[-1][key]
    ans=0
    for i,a in enumerate(A):
        b=1
        for key in p_lis:
            b*=(key**(p_lis[key]-p_a_lis[i].get(key,0)))%mod
        ans=(ans+b)%mod
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def prime_fact(m):
    pf={}
    for i in range(2,int(m**0.5)+1):
        while m%i==0:
            pf[i]=pf.get(i,0)+1
            m//=i
    if m>1:pf[m]=1
    return pf

def main():
    n=int(input())
    A=list(map(int,input().split()))
    p_lis={}
    for a in A:
        p_a=prime_fact(a)
        for key in p_a:
            if not p_lis.get(key,False) or p_lis[key]<p_a[key]:
                p_lis[key]=p_a[key]
    k=1
    for key in p_lis:
        k*=key**p_lis[key]
    ans=0
    for a in A:
        ans=(ans+k//a)%(10**9+7)
    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#E
def Primefact(n):
    Dic={}
    for i in range(2,int(pow(n,0.5))+1):
        if n%i==0:
            Dic[i]=0
            while True:
                n/=i
                Dic[i]+=1
                if n%i!=0:
                    break
        if n==1:
            break
    if n!=1:
        Dic[int(n)]=1
    return Dic

N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

Prime={}
for i in range(N):
    D=Primefact(A[i])
    for key,v in D.items():
        if key in list(Prime.keys()):
            Prime[key]=max(Prime[key],v)
        else:
            Prime[key]=v
ans=0
for i in range(N):
    B=1
    D=Primefact(A[i])
    for key,v in Prime.items():
        if key in list(D.keys()):
            v-=D[key]
        B*=key**v
        B%=mod
    ans+=B
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

x=int(input())
a=list(map(int, input().split()))
ans=0
if x==1:
	print(1)
else:
	chk=lcm(a[0],a[1])
	for i in range(x):
		chk=lcm(chk,a[i])
	for i in range(x):
		ans=(ans+(chk//a[i]))%(10**9+7)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a // fractions.gcd(a, b) * b

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]%mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
input=sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))

def gcd(a, b):
    return a if b == 0 else gcd(b, a%b)

def lcm(a, b):
    return a // gcd(a, b) * b

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]%mod

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

readline = stdin.readline
num = int(readline())
d = list(map(int, readline().split()))
k = 1
MOD = 1000000007
ans = 0
for a in d:
    k = lcm(k, a)
for a in d:
    ans += k // a % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def lcm(a, b):
    return (a * b) // gcd(a, b)

readline = stdin.readline
num = int(readline())
d = list(map(int, readline().split()))
k = d[0]
MOD = 1000000007
ans = 0
for i in range(1, num):
    k = lcm(k, d[i])
for i in range(num):
    ans += k // d[i] % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from sys import stdin

def lcm(a, b):
    return (a * b) // gcd(a, b)

readline = stdin.readline
num = int(readline())
d = list(map(int, readline().split()))
k = d[0]
MOD = 1000000007
ans = 0
for i in range(1, num):
    k = lcm(k, d[i])
for i in range(num):
    ans += k // d[i] % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from sys import stdin

def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    readline = stdin.readline
    num = int(readline())
    d = list(map(int, readline().split()))
    k = 1
    MOD = 1000000007
    ans = 0
    for a in d:
        k = lcm(k, a)
    for a in d:
        ans += k // a % MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a, b):
    return a // gcd(a, b) * b

def main():
    num = int(input())
    d = list(map(int, input().split()))
    k = 1
    MOD = 1000000007
    ans = 0
    for a in d:
        k = lcm(k, a)
    for a in d:
        ans += k // a % MOD
    print(ans % MOD)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))

    MOD = 10**9+7

    from collections import Counter

    def prime(n):
        p = Counter()

        while not n % 2:
            p[2] += 1
            n //= 2
            
        i = 3
        
        while i <= n**0.5:
            while not n % i:
                p[i] += 1
                n //= i
            i += 2
            
        if n > 1: p[n] += 1
        
        return p

    c = Counter()
    for a in A:
        p = prime(a)

        for key, value in p.items():
            c[key] = max(c[key], value)

    n = 1
    for key, value in c.items():
        n *= key**value

    ans = 0
    for a in A:
        ans += n * pow(a, MOD-2, MOD) 
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
A = list(map(int, input().split()))

MOD = 10**9+7

from collections import Counter

def prime(n):
    p = Counter()

    while not n % 2:
        p[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            p[i] += 1
            n //= i
        i += 2
        
    if n > 1: p[n] += 1
    
    return p

c = Counter()
for a in A:
    p = prime(a)

    for key, value in p.items():
        c[key] = max(c[key], value)

n = 1
for key, value in c.items():
    n *= key**value

ans = 0
for a in A:
    ans += n * pow(a, MOD-2, MOD) 
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))

MOD = 10**9+7

from collections import Counter

def prime(n):
    p = Counter()

    while not n % 2:
        p[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            p[i] += 1
            n //= i
        i += 2
        
    if n > 1: p[n] += 1
    
    return p

c = Counter()
for a in A:
    p = prime(a)

    for key, value in p.items():
        c[key] = max(c[key], value)

n = 1
for key, value in c.items():
    n *= key**value

ans = 0
for a in A:
    ans += n // a
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(x,y):
  return (x*y) // gcd(x,y)
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
l = a[0]
for i in range(1,n):
  l = lcm(l,a[i])
ans = 0
for i in range(n):
  ans += (l//a[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

import fractions
import collections
a = collections.deque(list(map(int, input().split())))
 
lcm = a.popleft()
a.append(lcm)
for i in range(1, n):
    tem = a.popleft()
    lcm = lcm * tem // fractions.gcd(lcm, tem)
    a.append(tem)
 
ans = 0
for i in range(n):
    tem = a.popleft()
    ans += lcm // tem
 
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
import fractions

def factorization(n):
    arr = dict()
    temp = n
    for i in range(2, int(n**0.5//1)+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt

    if temp!=1:
        arr[temp] = 1

    if arr==[]:
        arr[n] = 1

    return arr

a_fac = []
lcm_fac = dict()
for i in range(n):
    tem = factorization(a[i])
    a_fac.append(tem)
    for fac in tem.keys():
        if fac in lcm_fac.keys():
            lcm_fac[fac] = max(tem[fac], lcm_fac[fac])
        else:
            lcm_fac[fac] = tem[fac]


ans = 0
for i in range(n):
    tem = 1
    for j in lcm_fac.keys():
        if j in a_fac[i].keys():
            tem *= j ** (lcm_fac[j] - a_fac[i][j])
        else:
            tem *= j ** lcm_fac[j]
    ans += tem

print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
import fractions

lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

b = [0]*n
for i in range(n):
    b[i] = lcm//a[i]

print(sum(b) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
import fractions

lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

b = [0]*n
for i in range(n):
    b[i] = lcm//a[i]

print(sum(b) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
c=0
N=int(input())
L=list(map(int,input().split()))
a=L[0]
for i in range(1,N):
  a=(L[i]*a)//fractions.gcd(L[i], a)
for i in range(N):
  c=(c+(a//L[i]))%(10**9+7)
print(c)

Submission status: Time Limit Exceeded

Solution code:
import fractions
c=0
N=int(input())
L=list(map(int,input().split()))
a=L[0]
for i in range(N):
  a=(L[i]*a)//fractions.gcd(L[i], a)
for i in range(N):
  c=(c+(a//L[i]))%(10**9+7)
print(c)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from fractions import gcd
from collections import defaultdict
from copy import deepcopy

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7

p = [1]*(1001)
P = []  #1000までの素数表
p[0] = p[1] = 0
for x in range(2, int(sqrt(1000000))+1):
    if p[x]:
        P.append(x)
        for y in range(x*x, 1001, x):
            p[y] = 0

B = [defaultdict(int) for i in range(N)]  #N個の数を素因数分解したもの
lcm = defaultdict(int)  #N個の数のlcmを素因数分解したもの

for i in range(N):
    for j in P:
        if A[i] % j == 0:
            while A[i] % j == 0:
                A[i] //= j
                B[i][j] += 1
        lcm[j] = max(lcm[j],B[i][j])
    if A[i] != 1:
        B[i][A[i]] = 1
        lcm[A[i]] = 1

l = 1  #N個の数のlcm
for i in lcm.keys():
    l = (l*pow(i,lcm[i],mod)) % mod

ans = 0
#l/A[i]の和を求めていく
for i in range(N):
    r = l
    for j in list(B[i].keys()):
        r = (r*pow(j,mod-B[i][j]-1,mod)) % mod
    ans = (ans + r) % mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7


def modinv(a, mod):
    return pow(a, mod - 2, mod)


# 素因数分解
def prime_factor(n):
    # (素因数, 数)のリストで出てくる
    d = defaultdict(int)
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            d[i] += 1
            n //= i
    if n != 1:
        d[n] += 1
    return list(d.items())


n = int(input())
if n == 1:
    print(1)
    exit()
A = list(map(int, input().split()))
LCM = defaultdict(int)
for i in range(n):
    temp = prime_factor(A[i])
    for key, value in temp:
        t = LCM[key]
        LCM[key] = max(t, value)
lcm = 1
for key, val in LCM.items():
    lcm *= pow(key, val)
ans = 0
for i in range(n):
    gyaku = modinv(A[i], mod)
    ans += lcm * gyaku
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
def fact(n, factors):
    rtn = factors
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if i in rtn:
                rtn[i] = max(rtn[i],cnt)
            else:
                rtn[i] = cnt

    if temp!=1:
        if temp in rtn:
            rtn[temp] = max(rtn[temp],1)
        else:
            rtn[temp] = 1

    return rtn

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    LCM = 1
    factors = {}
    for a in A:
        factors = fact(a,factors)
    for k,v in factors.items():
        LCM *= pow(k,v,MOD)
    for a in A:
        ans += (LCM//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
def fact(n, factors, l):
    rtn = factors
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if i in rtn:
                k = rtn[i]
                rtn[i] = max(rtn[i],cnt)
                l *= pow(i,max(0,cnt-k),MOD)
            else:
                rtn[i] = cnt
                l *= pow(i,cnt,MOD)

    if temp!=1:
        if temp in rtn:
            k = rtn[temp]
            rtn[temp] = max(rtn[temp],1)
            l *= pow(i,max(0,1-k),MOD)
        else:
            rtn[temp] = 1
            l *= pow(temp,1,MOD)

    return rtn,l

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    LCM = 1
    factors = {}
    for a in A:
        factors,LCM = fact(a,factors,LCM)
    for a in A:
        ans += (LCM//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
def fact(n, factors):
    rtn = factors
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            if i in rtn:
                rtn[i] = max(rtn[i],cnt)
            else:
                rtn[i] = cnt

    if temp!=1:
        if temp in rtn:
            rtn[temp] = max(rtn[temp],1)
        else:
            rtn[temp] = 1

    return rtn

def lcm(factors,MOD):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    for k,v in factors.items():
        lcm *= pow(k,v,MOD)
    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    factors = {}
    for a in A:
        factors = fact(a,factors)
    L = lcm(factors,MOD)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
factmemo = [{} for _ in range((10**6+1))]
def fact(n):
    dict = factmemo[n]
    if dict!={}:
        return factmemo[n]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

    if temp!=1:
        dict[temp] = 1

    if dict=={}:
        dict[n] = 1

    factmemo[n] = dict

    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
def fact(n):
    dict = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

    if temp!=1:
        dict[temp] = 1

    if dict=={}:
        dict[n] = 1

    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)%MOD
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)%MOD

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
def fact(n):
    dict = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

    if temp!=1:
        dict[temp] = 1

    if dict=={}:
        dict[n] = 1

    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys

input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7


def modinv(a, mod):
    return pow(a, mod - 2, mod)


n = int(input())
if n == 1:
    print(1)
    exit()
A = list(map(int, input().split()))
lcm = A[0]
for i in range(n):
    g = gcd(lcm, A[i])
    lcm = lcm * A[i] // g
ans = 0
for i in range(n):
    gyaku = modinv(A[i], mod)
    ans += lcm * gyaku
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys

input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception("modular inverse does not exist")
    else:
        return x % m


n = int(input())
if n == 1:
    print(1)
    exit()
A = list(map(int, input().split()))
lcm = A[0]
for i in range(n):
    g = gcd(lcm, A[i])
    lcm = lcm * A[i] // g
ans = 0
for i in range(n):
    gyaku = modinv(A[i],mod)
    ans += lcm * gyaku
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def computeGCD(x, y): 
    t = x if x < y else y
    while t >= 1:
        if x % t or y % t:
            t -= 1
        else:break 
              
    return t

def lcm(arr):
    lcm = arr[0]
    for i in range(1,len(arr)):
        lcm = lcm*arr[i]//computeGCD(lcm, arr[i])
    return lcm

n = input()
arr = list(map(int, input().split()))
modd = 10**9+7
val = lcm(arr)

s = 0
for i in arr:
    s = (s + val // i) % modd
print(s)

Submission status: Time Limit Exceeded

Solution code:
def computeGCD(x, y): 
    t = x if x < y else y
    while t >= 1:
        if x % t or y % t:
            t -= 1
        else:break 
              
    return t

def lcm(arr):
  lcm = arr[0]
  for i in range(1,len(arr)):
    lcm = lcm*arr[i]//computeGCD(lcm, arr[i])
  return lcm

n = input()
arr = list(map(int, input().split()))
modd = 10**9+7
val = lcm(arr)

print(sum(val//i for i in arr) % modd)

Submission status: Time Limit Exceeded

Solution code:
def computeGCD(x, y): 
    t = x if x < y else y
    while t >= 1:
        if x % t or y % t:
            t -= 1
        else:break 
              
    return t

def lcm(a, b):
    return a * b // computeGCD(a, b)

n = input()
arr = list(map(int, input().split()))
modd = 10**9+7
val = 1
for i in arr:
    val = lcm(val, i)

print(sum(val//i for i in arr) % modd)

Submission status: Time Limit Exceeded

Solution code:
def computeGCD(x, y): 
    if x > y: 
        small = y 
    else: 
        small = x 
    for i in range(1, small+1): 
        if((x % i == 0) and (y % i == 0)): 
            gcd = i 
              
    return gcd 

def lcm(a, b):
    return a * b // computeGCD(a, b)

n = input()
arr = list(map(int, input().split()))
modd = 10**9+7
val = 1
for i in arr:
    val = lcm(val, i)

print(sum(val//i for i in arr) % modd)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def main():

    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9 + 7

    lcm = 1
    for a in A:
        lcm = lcm * a // gcd(lcm, a)


    ans = 0
    for a in A:
        ans += lcm // a

    print(ans % MOD)    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)


ans = 0
for a in A:
    ans += lcm // a

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)


ans = 0
for a in A:
    ans += lcm // a
    if ans >= MOD:
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(raw_input())
elems = map(int, raw_input().split(' '))
def gcd( a, b ):
	return gcd(b, a % b)  if b else a

def lcm(a,b):
	return a*b/ gcd(a,b)

lcm = reduce(lcm, elems)
cumul = 0
for e in elems:
	cumul += lcm / e
	cumul %= (10 ** 9) + 7
print cumul

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
#n=10000
#a=list(range(10**6,10**6-n,-1))
import fractions 
mod=pow(10,9)+7

b=[a,[]]
pre=0
now=1
while len(b[pre])>1:
  for i in range(0,len(b[pre])-1,2):
    b[now].append((b[pre][i]*b[pre][i+1])//fractions.gcd(b[pre][i],b[pre][i+1]))
  if len(b[pre])%2==1:
    b[now].append(b[pre][-1])
  b[pre]=[]
  now,pre=pre,now

lcma=b[pre][0]
ans=0
for ai in a:
  ans+=((lcma//ai))%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
import fractions 
mod=pow(10,9)+7
lcma=1
for ai in a:
  lcma*=ai//fractions.gcd(lcma,ai)
ans=0
for ai in a:
  ans+=((lcma//ai))%mod
  ans%=mod
print(ans)