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:
import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = 10**9+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  m = A[0]
  for i in range(1, n):
    m = m // gcd(m, A[i]) * A[i]
  ans = 0
  for i in range(n):
    ans += m//A[i]
  print(ans%mod)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
import fractions
# def gcd(a,b):
#   while b != 0:
#     a, b = b, a % b
#   return a
# 最小公倍数
def lcm(a,b):
    return (a*b) // fractions.gcd(a,b)

g = 1
for i in range(n):
    g = lcm(g, s[i])
for i in range(n):
    ans += g // s[i] % mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
g=lambda x,y:x if y<1else g(y,x%y)
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//g(s,t)
print(sum(s//i for i in a)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:

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

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

N = int(input())
A = list(map(int, input().split()))
l = A[0]
for a in A:
    l = lcm(l, a)
ans = 0
mod = 10**9+7
for a in A:
    ans += (l * pow(a, mod-2, mod))%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = 10**9+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  m = A[0]
  for i in A[1:]:
    m = m // gcd(m, i) * i
  ans = 0
  for i in A:
    ans += m//i
  print(ans%mod)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007

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

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

n = int(input())
a = list(map(int,input().split()))
all_lcm = 1
for i in range(n):
    all_lcm = lcm(all_lcm, a[i])
ans = 0
for i in range(n):
    ans += all_lcm//a[i]
print(ans%MOD)

Submission status: Time Limit Exceeded

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**6)
for i in range(2,10**6):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**6,i):
        is_prime[j]=False

F=[[0 for _ in range(len(primes))] for __ in range(N)]
LCM=[0 for _ in range(len(primes))]
for i in range(N):
    n=A[i]
    for j,p in enumerate(primes):
        while n%p==0:
            F[i][j]+=1
            LCM[j]=max(LCM[j],F[i][j])
            n//=p

ans=0
for i in range(N):
    tmp=1
    for j,p in enumerate(primes):
        tmp=tmp*pow(p,LCM[j]-F[i][j],MOD)%MOD
    ans=(ans+tmp)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = 10**9+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  cnt = 0
  m = A[0]
  for i in A[1:]:
    m = m // gcd(m, i) * i
  ans = 0
  for i in A:
    ans += m//i
    ans %= mod
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))

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

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

Submission status: Time Limit Exceeded

Solution code:

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

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

N = int(input())
A = list(map(int, input().split()))
l = A[0]
for a in A:
    l = lcm(l, a)
ans = 0
mod = int(1e9+7)
for a in A:
    ans += (l * pow(a, mod-2, mod))%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result=(result+ans//item)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import*
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//gcd(s,t)
c=0
for i in a:c+=s//i
print(c%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
for a in As:
    if a == 1:
        continue
    factors = factorization(a)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    # lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod
print((lcm*a)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = list(map(int, input().split()))
mod=pow(10,9)+7

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

v=lcm(*c)
ans=0

for i in range(n):
    ans+=v//c[i]

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions


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


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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))

lcm_A = A[0]
for i in range(1, N):
    lcm_A = lcm_A * A[i] // gcd(lcm_A, A[i])

ans = 0
for i in range(N):
    ans += lcm_A // A[i]

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = 10**9+7
def lcm(x, y):
  return x//gcd(x, y)*y
def main():
  n = int(input())
  A = list(map(int, input().split()))
  cnt = 0
  m = A[0]
  for i in A[1:]:
    m = lcm(m, i)
  ans = 0
  for i in A:
    ans += m//i
    ans %= mod
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def main():

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

    def primes(n):
        b = [True] * (n//2)
        for i in range(3, int(n**0.5)+1, 2):
            if b[i//2]:
                b[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)

        return [2] + [2*i + 1 for i in range(1, n//2) if b]

    def isprime(n):
        if n == 1: return False
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True

    ps = primes(int(math.sqrt(max(A))) + 1)

    d = dict()
    di = collections.defaultdict(dict)
    for i in range(N):
        if isprime(A[i]):
            if A[i] not in d:
                d[A[i]] = 1
            di[i][A[i]] = 1
        else:
            v = A[i]
            for p in ps:
                if p > v:
                    break
                cnt = 0
                while v > 1 and v % p == 0:
                    cnt += 1
                    v //= p
                if p in d:
                    d[p] = max(d[p], cnt)
                else:
                    d[p] = cnt
                di[i][p] = cnt
            if v > 1:
                di[i][v] = 1
                if v not in d:
                    d[v] = 1

    ans = 0
    for i in range(N):
        b = 1
        for p in d:
            if p in di[i]:
                b *= pow(p, d[p]-di[i][p])
            else:
                b *= pow(p, d[p])
            b %= mod
        ans += b
        ans %= mod

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007

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

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

n = int(input())
a = list(map(int,input().split()))
all_lcm = 1
for i in range(n):
    all_lcm = lcm(all_lcm, a[i])
ans = 0
for i in range(n):
    ans += all_lcm//a[i]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7

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

ans=0
for i in range(n):
  ans=(ans+lcm//A[i])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import*
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//gcd(s,t)
print(sum(s//i for i in a)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
  from functools import reduce
  ans = 0
  n = int(input())
  b = tuple(map(int, input().split()))
  b_ = tuple(set(b))
  ov = 10**9+7
  from fractions import gcd
  def lcm(x,y):
    return (x * y) // gcd(x, y)
  def lcm_list(a):
    return reduce(lcm, a, 1)
  l = lcm_list(b_)
  for i in b:
    ans += l//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007

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

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    all_lcm = a[0]
    for i in range(n):
        all_lcm = lcm(all_lcm, a[i])
    ans = 0
    for i in range(n):
        ans += all_lcm//a[i]
    print(ans%MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans+=l//a
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
MOD = 10**9+7
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)  

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
ans = 0
for ai in aa:
  ans += l//ai % MOD

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:

def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result=(result+ans//item)%(10**9+7)

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
import fractions

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]

INL=LI()
LCM={}
for i in INL:
    for p in primes:
        cnt = 0
        while i%p == 0:
            i //= p
            cnt += 1
        if not p in LCM: LCM[p] = 0
        LCM[p] = max(LCM[p], cnt)
    if i != 1:
        if not i in LCM: LCM[i] = 0
        LCM[i] = max(LCM[i], 1)

res = 0
for i in INL:
    num = 1
    for p, cnt in LCM.items():
        if cnt:
            cnt2 = 0
            while i % p == 0:
                i //= p
                cnt2 += 1
            num *= p**(cnt - cnt2)
    res += num

# print(LCM)
print(res%DVSR)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
n = int(input())


l = list(map(int ,input().split()))

lc = 1

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


for i in range(n):
    lc = lcm(lc,l[i])
ans = 0
for i in range(n):
    ans+=lc//l[i]
    ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
import fractions

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()

primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997]

INL=LI()
LCM={}
for i in INL:
    for p in primes:
        cnt = 0
        while i%p == 0:
            i //= p
            cnt += 1
        if not p in LCM: LCM[p] = 0
        LCM[p] = max(LCM[p], cnt)
    if i != 1:
        if not i in LCM: LCM[i] = 0
        LCM[i] = max(LCM[i], 1)

res = 0
for i in INL:
    num = 1
    for p, cnt in LCM.items():
        cnt2 = 0
        while i % p == 0:
            i //= p
            cnt2 += 1
        num *= p**(cnt - cnt2)
    res += num

# print(LCM)
print(res%DVSR)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
l=1
for a in A:
  l=lcd(l,a)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import fractions
import numpy as np
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in a:
    div = div*i//fractions.gcd(div, i)

ans = 0
for i in a:
    ans += div//i

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    while b:
        a,b==b,a%b
    return a
def lcm(a,b):
    return a//gcd(a,b)*b
 
n=int(input())
a=[int(i) for i in input().split()]
L=a[0]
for i in a:
    if L%i!=0:
        L=lcm(L,i)
L%=(10**9+7)
ans=0
for i in a:
    ans=(ans+L//i)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
n = int(input())
al = list(map(int,input().split()))

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

p = lcm_list(al)

ans = 0

for a in al:
    ans += p // a
    ans %= 10**9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:

MOD = 1000000007

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

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    all_lcm = a[0]
    for i in range(n):
        all_lcm = lcm(all_lcm, a[i])
    ans = 0
    for i in range(n):
        ans += all_lcm//a[i]
        ans %= MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
n = int(input())


l = input().split()
for i in range(n):
    l[i] = int(l[i])
lc = 1

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


for i in range(n):
    lc = lcm(lc,l[i])
ans = 0
for i in range(n):
    ans+=lc//l[i]
    ans%=1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
def main():

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

    def primes(n):
        b = [True] * (n//2)
        for i in range(3, int(n**0.5)+1, 2):
            if b[i//2]:
                b[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)

        return [2] + [2*i + 1 for i in range(1, n//2) if b]

    def isprime(n):
        if n == 1: return False
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0:
                return False
        return True

    ps = primes(int(math.sqrt(max(A))) + 1)

    d = dict()
    di = collections.defaultdict(dict)
    for i in range(N):
        if isprime(A[i]):
            if A[i] not in d:
                d[A[i]] = 1
            di[i][A[i]] = 1
        else:
            v = A[i]
            for p in ps:
                cnt = 0
                while v > 0 and v % p == 0:
                    cnt += 1
                    v //= p
                if p in d:
                    d[p] = max(d[p], cnt)
                else:
                    d[p] = cnt
                di[i][p] = cnt
            if v > 1:
                di[i][v] = 1
                if v not in d:
                    d[v] = 1

    ans = 0
    for i in range(N):
        b = 1
        for p in d:
            if p in di[i]:
                b *= pow(p, d[p]-di[i][p])
            else:
                b *= pow(p, d[p])
            b %= mod
        ans += b
        ans %= mod

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:

import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y)%(prime), an ,0 )

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E
import fractions
N = int(input()) 
A = list(map(int, input().split()))

def main():
    value = A[0]
    for i in range(1, N):
        value = value * A[i] // fractions.gcd(value, A[i])

    z = 10**9+7
    ans = 0
    for i in A:
        ans += (value//i) % z

    print(ans % z)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions as m
from functools import reduce
n = int(input())
a = list(map(int,input().split()))
ans = 0
mod = 10**9+7
def lcm(x,y):
    return (x*y//m.gcd(x,y))
def lcml(nums):
    return reduce(lcm,nums,1)
l = lcml(a)
for x in a:
    ans+= (l*pow(x,mod-2,mod)) %mod
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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


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

l = reduce(lcm, A, 1)
ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x

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

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

l = 1
for x in a:
    l = lcm(x, l)

ans = 0
for x in a:
    ans += l//x

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

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce


def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))


sys.setrecursionlimit(10 ** 9)
INF = float('inf')


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def solve(N, As):
    l = lcm_list(As)
    return sum([(l // a) % mod for a in As]) % mod

mod = 10 ** 9 + 7

N = INT()
As = LIST()

print(solve(N, As))

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce


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


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
    ans %= (10**9 + 7)
print(ans)

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 // gcd(lcm,a) * a

ans = 0
for a in A:
    ans += lcm // a
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

def P(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

dictlist = []
for i in range(N):
    dictlist.append(P(A[i]))

dict = dictlist[0].copy()
for i in range(1,N):
    new = dictlist[i]
    for k in new.keys():
        if k not in dict:
            dict[k]=new[k]
        elif dict[k]<new[k]:
            dict[k]=new[k]

output = 0
for i in range(N):
    out = 1
    tmp = dictlist[i]
    for k in dict.keys():
        if k in tmp:
            G = dict[k]-tmp[k]
        else:
            G = dict[k]
        out *= int(k)**G %(10**9+7)
    output += out %(10**9+7)
    output = output % (10**9+7)
print(output)

Submission status: Time Limit Exceeded

Solution code:

import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y)%(prime*10000), an ,0 )

print(ans%prime)

Submission status: Time Limit Exceeded

Solution code:
from fractions import*
def main():
    _,a=open(0)
    *a,=map(int,a.split())
    s=1
    for i in a:s*=i//gcd(s,i)
    c=0
    for i in a:
        c+=s//i
        c%=10**9+7
    print(c)
main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=sorted(list(map(int,input().split())))
l=1
for a in A:
  l=lcd(l,a)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)
ans = 0

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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


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

l = reduce(lcm, A)
ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import fractions
 
from functools import reduce
 
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
 
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
 
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
 
def LI():
  return [int(s) for s in input().split()]
 
 
input = sys.stdin.readline
ri = lambda: int(input())
ril = lambda: list(map(int, input().split()))
 
N = ri()
A_s = ril()
mod = 10**9 + 7
 
l = lcm_list(A_s)
 
print(sum(map(lambda x : l//x, A_s)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

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

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

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

lcm_a = 1

for i in range(N):
    lcm_a = lcm(lcm_a,A[i])

B = np.array([])
for i in range(N):
    B = np.append(B,lcm_a//A[i])

mod = int(1e9+7)
print(int((np.sum(B)%mod)))

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(l,a)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import*
M=10**9+7
_,a=open(0)
*a,=map(int,a.split())
s=1
for t in a:s*=t//gcd(s,t)
c=0
for i in a:
    c+=s//i
    if c>M:c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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


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


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

l = reduce(lcm, A)
ans = 0
for a in A:
  ans += (l//a) % MOD
  ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import fractions
import numpy as np
 
mod = 10**9+7
 
n = int(input())
a = list(map(int, input().split()))
 
div = a[0]
for i in range(1, n):
    div = div*a[i]//fractions.gcd(div, a[i])

ans = 0
for i in range(n):
    ans += div//a[i]

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(l,a%1000000007)
ans=0
for a in A:
  ans=(ans+l//a)
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
import collections

P=collections.defaultdict(int)
PI=[collections.defaultdict(int) for _ in range(n)]
for i in range(n):
  a=A[i]
  for j in range(2,int(a**0.5)+1):
    while a%j==0:
      PI[i][j]+=1
      a//=j
  if a>1:
    PI[i][a]=1
  for p in PI[i].keys():
    P[p]=max(P[p],PI[i][p])
ans=0
for i in range(n):
  mul=1
  for p in P.keys():
    mul=(mul*pow(p,P[p]-PI[i][p],mod))%mod


  ans=(ans+mul)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# E
import fractions
N = int(input()) 
A = list(map(int, input().split()))

value = A[0]
for i in range(1, N):
    value = value * A[i] // fractions.gcd(value, A[i])

z = 10**9+7
ans = 0
for i in A:
    ans += (value//i) % z

print(ans % z)