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:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
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
lists=[prime_factorize(lis[i]) for i in range(n)]
C=Counter([])
for i in range(n):
    x=Counter(lists[i])
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=Counter(lists[i])
    y=1
    for j in C.keys():
        y=y*pow(j,C[j]-x[j],mod)
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
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
C=Counter([])
for i in range(n):
    x=Counter(prime_factorize(lis[i]))
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=Counter(prime_factorize(lis[i]))
    y=1
    for j in C.keys():
        y=y*pow(j,C[j]-x[j],mod)
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
ans=0
for i in range(n):
    ans=(ans+LCM//lis[i])%mod
print(ans)
'''for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)'''

Submission status: Time Limit Exceeded

Solution code:
from __future__ import division, print_function

import sys
from atexit import register

if sys.version_info[0] < 3:
    from io import BytesIO as stream
else:
    from io import StringIO as stream


sys.stdin = stream(sys.stdin.read())
input = lambda: sys.stdin.readline().rstrip('\r\n')

sys.stdout = stream()
register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

from collections import Counter

def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    n = read_int()
    A = read_ints()
    MAX = max(A)+1 # 10**6+1
    count = [Counter() for i in range(MAX)]
    modulo = 10**9+7
    # disassemble all numbers up to 10**6
    for number in range(2, MAX):
        if len(count[number]) > 0: # not prime
            continue
        for step in range(number, MAX, number):
            temp = number
            while step%temp == 0:
                count[step][number] += 1
                temp *= number
    max_counter = Counter()
    for a in A:
        for k, v in count[a].items():
            max_counter[k] = max(max_counter[k], v)
    answer = 0
    for a in A:
        B = 1
        for k, v in max_counter.items():
            B = (B*k**(v-count[a][k]))%modulo
        answer = (answer+B)%modulo
    return answer


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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    n = read_int()
    A = read_ints()
    MAX = max(A)+1 # 10**6+1
    count = [Counter() for i in range(MAX)]
    modulo = 10**9+7
    # disassemble all numbers up to 10**6
    for number in range(2, MAX):
        if len(count[number]) > 0: # not prime
            continue
        for step in range(number, MAX, number):
            temp = number
            while step%temp == 0:
                count[step][number] += 1
                temp *= number
    max_counter = Counter()
    for a in A:
        for k, v in count[a].items():
            max_counter[k] = max(max_counter[k], v)
    answer = 0
    for a in A:
        B = 1
        for k, v in max_counter.items():
            B = (B*k**(v-count[a][k]))%modulo
        answer = (answer+B)%modulo
    return answer


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)
#### 
# https://note.nkmk.me/python-gcd-lcm/
from math import gcd
from functools import reduce

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)
  
L = lcm_list(A)
ans = 0
for a in A:
  ans += L // a
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
#for p in lcm_pf:
#    lcm = lcm * (p ** lcm_pf[p])
import math
for v in a:
    lcm = (lcm // math.gcd(lcm, v)) * v

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import functools

@functools.lru_cache(maxsize=10 ** 6)
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

@functools.lru_cache(maxsize=10 ** 6)
def lcm(a, b):
    return (a // gcd(a, b)) * b

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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):
    return (a // gcd(a, b)) * b

a_lcm = 1
for v in a:
    a_lcm = lcm(a_lcm, v)

ans = 0
for v in a:
    ans = (ans + (a_lcm // v)) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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 is_prime
prime = primes(MAX)
pri = [i for i in range(2,MAX+1) if prime[i]]
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = defaultdict(int)
    temp = n
    for i in range(2,int(n**0.5)+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 len(arr) == 0:
        arr[n] = 1
    return arr
c = factorization(A[0])
for i in range(1,N):
    nex = factorization(A[i])
    for j in pri:
        aa = max(c[j],nex[j])
        c[j] = aa
ans = 0
for i in range(N):
    a = A[i]
    p = factorization(a)
    plus = 1
    for j in pri:
        plus *= pow(j,c[j]-p[j],MOD)
    ans += plus
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
MAX = max(A)
def primes(n):#nまでの素数を列挙0は入れちゃダメ
    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 is_prime
prime = primes(MAX)
pri = [i for i in range(2,MAX+1) if prime[i]]
def factorization(n): #2以上の整数n => [[素因数, 指数], ...]の2次元リストを返す
    arr = defaultdict(int)
    temp = n
    for i in range(2,int(n**0.5)+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 len(arr) == 0:
        arr[n] = 1
    return arr
c = factorization(A[0])
for i in range(1,N):
    nex = factorization(A[i])
    for j in pri:
        aa = max(c[j],nex[j])
        c[j] = aa
ans = 0
for i in range(N):
    a = A[i]
    p = factorization(a)
    plus = 1
    for j in pri:
        plus *= pow(j,c[j]-p[j],MOD)
    ans += plus
    ans %= MOD
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
 
def lcm(a,b):
  g = gcd(a, b)
  return a*b // g
 
l = 1
for a in A:
  l = lcm(l, a)
 
# print(l)
 
ans = 0
for a in A:
  ans += l//a
  ans %= MOD
 
print(ans)

Submission status: Time Limit Exceeded

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

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

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

# print(l)

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

print(ans)

Submission status: Time Limit Exceeded

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

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

p = 1000000007

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
def lcm(l,r):
    g=gcd(l,r)
    res=(l//g)*(r//g)*g
    return res
l=1
r=10**6
res=a[0]
for i in a:
    res=lcm(res,i)
ans=0
for i in a:
    ans+=(res//i)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
def lcm(a, b):
    return (a * b // gcd(a, b))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] > Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


show_flg=False
show_flg=True

n=I()
a=sorted(LI())

N=10**3
prs=PrimeNumSet(N)

l=defaultdict(int)
for i in range(n):
    t=a[i]
    for p in prs:
        if t%p==0:
            c=0
            while t%p==0:
                t//=p
                c+=1
            l[p]=max(l[p],c)
    if t!=1:
        l[t]=1
L=1
for i,j in l.items():
    L*=i**j

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] > Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


show_flg=False
show_flg=True

n=I()
a=sorted(LI())

l=1
for i in range(n):
    g=gcd(l,a[i])
    l=l//g*a[i]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################

## return the list of prime numbers in [2,N], using eratosthenes sieve
## around 800 ms for N = 10**6  by PyPy3 (7.3.0) @ AtCoder
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] > Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum


show_flg=False
show_flg=True

n=I()
a=LI()

l=1
for i in range(n):
    g=gcd(l,a[i])
    l=l//g*a[i]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def soin(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

n = int(input())
a = list(map(int,input().split()))
p = {}
g = []
mod = 10**9 + 7

for i in range(n):
    g.append(soin(a[i]))
    for k , v in g[i].items():
        if v > p.get(k,0):
            p[k] = v
ans = 0
for i in range(n):
    now = 1
    for k , v in p.items():
        now *= pow(k,p[k]-g[i].get(k,0),mod)
        now %= mod
    ans += now
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
g = a[0]
mod = 10**9 + 7
for i in range(1,n):
    g = (g*a[i])//math.gcd(g,a[i])
ans = 0
for i in range(n):
    ans += g//a[i]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys


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


input = sys.stdin.readline
n = int(input())
A = list(map(int, input().split()))
LCM = 1
ans = 0
MOD = 1000000007
for x in A:
  LCM = lcm(LCM, x)
for x in A:
  ans += LCM // x
  ans %= MOD

print(ans)