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 numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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


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


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

    mod = 10 ** 9 + 7

    res = 0
    L = A[0]

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

    for i in range(N):
        res += L // A[i]
        res %= mod

    print(res)



main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a // x % mod for x in A) % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
_,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
    c%=10**9+7
print(c)

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*100), an ,0 )

print(ans%prime)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

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

# lcmTotal = 1
# for i in numList:
#   lcmTotal = lcm_base(lcmTotal, i)

lcmTotal = lcm_list(numList)

result = 0
for targetNum in numList:
  result += lcmTotal // targetNum % mod

print(result % mod)

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


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

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()
ans = l[0]*l[1]/fractions.gcd(l[0],l[1])
for i in range(2,n):
    ans = ans*l[i]/fractions.gcd(ans,l[i])

mod = 10**9+7
a = 0
for i in range(n):
    a += ans//l[i]
    a %= mod
print(int(a%mod))

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*10), an ,0 )

print(ans%prime)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(a):
    ans = a[0]
    
    for i in range(1,len(a)):
        ans = (ans//gcd(ans,a[i]))*a[i]
    
    return ans

N = int(input())
A = list(map(int,input().split(" ")))
g = lcm(A)
ans = 0
mod = 10**9+7

for i in A:
    ans += (g//i)%(mod)

print(ans%mod)

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):
    tdict = dict.copy()
    out = 1
    tmp = dictlist[i]
    for k in tmp.keys():
        tdict[k] = tdict[k]-tmp[k]
    for k in tdict.keys():
        out *= int(k)**tdict[k] %(10**9+7)
    output += out %(10**9+7)
    output = output % (10**9+7)
print(output)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from functools import reduce


class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n
            complexity: O(n^(1/2))
            used in ProjectEuler No.12, yukicoder No.36
        """
        assert(n >= 1)
        number = n
        if number == 1:
            self.primeFactorization = {}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])


mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
divs = [Divisor(a) for a in A]
lcm = {}
for div in divs:
    for p, cnt in div.primeFactorization.items():
        lcm[p] = max(lcm.get(p, 0), cnt)
ans = 0
for div in divs:
    ret = 1
    for key, val in lcm.items():
        ret = ret * pow(key, val - div.primeFactorization.get(key, 0), mod) % mod
    ans = (ans + ret) % mod
print(ans)

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 = []
    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 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))))

    d = dict()
    di = collections.defaultdict(dict)
    for i in range(N):
        if isprime(A[i]):
            if A[i] in d:
                d[A[i]] = max(d[A[i]], 1)
            else:
                d[A[i]] = 1
            di[i][A[i]] = 1
        else:
            v = A[i]
            for p in ps:
                cnt = 0
                if p > math.sqrt(A[i]):
                    break
                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 in d:
                    d[v] = max(d[v], 1)
                else:
                    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])
                b %= mod
            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 sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
ans = [a // x % mod for x in A]
print(sum(ans) % mod)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if y==0:
        return x
    return gcd(y,x%y)

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if y==0:
        return x
    return gcd(y,x%y)

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
# lcm %= MOD
ans = 0
for i in A:
    ans += lcm*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)

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

if __name__ == '__main__':
    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:
from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        if x % a[i] != 0:
            x = (x * a[i]) // gcd(x, a[i])
    return x

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = [lcm_num//ai for ai in a]

print(sum(ans)%div)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
lcm = [0]*10**6
mod = 10**9+7
for a in A:
    n = 2
    while a != 1:
        c = 0
        while a % n == 0:
            a //= n
            c += 1
        lcm[n] = max(lcm[n], c)
        n += 1
l = 1
for i, n in enumerate(lcm):
    l *= pow(i, n, mod)
    n %= mod
ans = 0
for a in A:
    p = pow(a, mod-2, mod)
    ans += (l*p) % mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  def prime_factorize(n):
    a = []
    while n % 2 == 0:
      a.append(2)
      n //= 2
    f = 3
    while f * f <= n:
      if n % f == 0:
        a.append(f)
        n //= f
      else:
        f += 2
    if n != 1:
      a.append(n)
    return a
  def prime_dict(a):
    import collections
    c = collections.Counter(prime_factorize(a))
    return c

  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  c = {}
  for i in a:
    d = prime_dict(i)
    for k in d.keys():
      m = 0
      if k in c:
        if d[k] < c[k]:
          continue
      c[k] = d[k]
  lcm = 1
  for k,v in c.items():
    lcm *= k**v
  for i in a:
    ans += lcm//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
ans = 0

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

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

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

print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(a):
    ans = a[0]
    
    for i in range(1,len(a)):
        ans = (ans//gcd(ans,a[i]))*a[i]
    
    return ans

N = int(input())
A = tuple(map(int,input().split(" ")))
g = lcm(A)
ans = 0
mod = 10**9+7

for i in A:
    ans += (g//i)%(mod)

print(ans%mod)

Submission status: Time Limit Exceeded

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

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

mod = int(1e9 + 7)

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

l = a[0]
for i in range(1, n):
    l = lcm(l, a[i])

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)
for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    count+=pro//ai
    count%=mod
print(count)

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


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

li = [0] * (10 ** 6 + 1)
for e in a:
    l = factorization(e)
    for le in l:
        num, times = le
        li[num] = max(li[num], times)

ans = 0
for e in a:
    l = factorization(e)
    l2 = [0] * (10 ** 6 + 1)
    for le in l:
        num, times = le
        l2[num] = times

    b = 1
    for i, (lie, l2e) in enumerate(zip(li, l2)):
        b *= i ** (lie - l2e)

    ans += b
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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


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

N=int(input())
A=list(map(int,input().split()))
MOD=(10**9)+7
S=list(set(A))
LCM=lcm_list(S)
ans=0

for i in range(N):
    ans+=(LCM//A[i])
    ans=ans%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

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

mk = 1
for i in a:
    mk = lcm(mk, i)

k = 0
for j in a:
    k = (k +  mk // j) %MOD
print(k %MOD)

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
# from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
# from heapq import heappop, heappush, heappushpop
# from collections import Counter,defaultdict,deque
# from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
# from bisect import bisect_left,bisect_right
# from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    l = 1
    for a in A:
        l *= a//gcd(l,a)
    ans = 0
    for a in A:
        ans += l//a
        ans%=mod
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

P = 10**9 + 7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

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

    ans = ans%P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(a):
    ans = a[0]
    for i in range(1,len(a)):
        ans = (ans//gcd(ans,a[i]))*a[i]
    return ans

N = int(input())
A = tuple(map(int,input().split(" ")))
g = lcm(A)
ans = 0
for i in A:
    ans += g//i
    ans %= (10**9+7)

print(ans)

Submission status: Time Limit Exceeded

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

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

mod = int(1e9 + 7)

while True:
    try:
        n = int(input())
        a = list(map(int, input().split()))
    except:
        break

    l = a[0]
    for i in range(1, n):
        l = lcm(l, a[i])

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

MOD = 1000000007

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

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

lcm = 1
for i in A: lcm = LCM(lcm, i)

ans = 0
for i in A:
    ans += lcm // i
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m, n):
    while n > 0: m, n = n, m % n
    return m

def lcm(m, n):
    if m == 0 or n == 0: return 0
    return m // gcd(m, n) * n

MOD = 10**9 + 7

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

    if n == 1:
        print(1)
        return 0

    l = a[0]
    for i in range(1, n): l = lcm(l, a[i])
    res = 0
    for ai in a: res += l // ai % MOD
    print(res % MOD)

main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

mod = 10**9 + 7

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


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

Submission status: Time Limit Exceeded

Solution code:
def main():
  def prime_factorize(n):
    a = []
    while n % 2 == 0:
      a.append(2)
      n //= 2
    f = 3
    while f * f <= n:
      if n % f == 0:
        a.append(f)
        n //= f
      else:
        f += 2
    if n != 1:
      a.append(n)
    return a
  def prime_dict(a):
    import collections
    c = collections.Counter(prime_factorize(a))
    return c

  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  c = {}
  for i in a:
    d = prime_dict(i)
    for k in d.keys():
      m = 0
      if k in c:
        m = c[k]
      c[k] = max(d[k],m)
  lcm = 1
  for k,v in c.items():
    lcm *= k**v
  for i in a:
    ans += lcm//i%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
count=a[0]
for i in range(n-1):
    count=count*a[i+1]//fractions.gcd(count, a[i+1])
ans=0


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

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    l = 1
    for a in A:
        l *= a//gcd(l,a)
    ans = 0
    for a in A:
        ans += l//a
        ans%=mod
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

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

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(' ')))
lcm = A[0]
for i in A[1:]:
    lcm = lcm*i // gcd(lcm, i)

ans = 0
for i in range(len(A)):
    ans += lcm // A[i]
    ans = ans % 1000000007
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l_1 = 1
l_2 = 1
mod = 10**9+7
def lcm(x,y):
    return x*y//gcd(x,y)
for i in A[:N//2]:
    l_1 = lcm(l_1,i)
for j in A[N//2:]:
    l_2 = lcm(l_2,j)
l = lcm(l_1,l_2)

print(sum([l//i%mod for i in A])%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def is_prime(n):
    if n == 1:
        return False

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

    return True


def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




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


            


    




    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
from functools import reduce


class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n
            complexity: O(n^(1/2))
            used in ProjectEuler No.12, yukicoder No.36
        """
        assert(n >= 1)
        number = n
        if number == 1:
            self.primeFactorization = {}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])


mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
divs = [Divisor(a) for a in A]
lcm = {}
for div in divs:
    ps = set(div.primeFactorization.keys()) | set(lcm.keys())
    for p in ps:
        lcm[p] = max(div.primeFactorization.get(p, 0), lcm.get(p, 0))
ans = 0
for div in divs:
    ret = 1
    for key, val in lcm.items():
        ret = ret * pow(key, val - div.primeFactorization.get(key, 0), mod) % mod
    ans = (ans + ret) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

mod = 10**9 + 7

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
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)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
for i in A:
    ans += lcm // i
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

if N == 1:
    print(1)
    exit()

def saisho_ko_baisu(A,B):
    return A*B // gcd(A,B)
#     # A < B
#     x = A*B
#     r = B%A
#     while r!=0:
#         B = A
#         A = r
#         r = B%A
#     return x//A

A.sort(reverse = True)
tmp = saisho_ko_baisu(A[0], A[1])
res = tmp//A[0] + tmp//A[1]
for i in range(2,N):
    if tmp % A[i] != 0:
        new = saisho_ko_baisu(A[i], tmp)
        res *= new//tmp
        tmp = new
    res += tmp // A[i]

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

Submission status: Time Limit Exceeded

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

ans = 0
MOD = 10**9 + 7

LCM = A[0]
for i in range(1, N):
    LCM *= A[i]//fractions.gcd(LCM, A[i])
    
for a in A:
  ans += LCM//a
  
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	
	a=1
	for i in A:
		a=a*i//gcd(a, i)
	ans=0
	for i in A:
		ans+=(a//i)
		ans%=mod
	print(ans)
	
	
	
	
	
	


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from fractions import gcd
from functools import reduce

N = int(input())

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

L = reduce((lambda x, y: x // gcd(x, y) * y), A)

res = 0

MOD = 10**9+7

for a in A:
  res = (res + L//a % MOD) % MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))