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:
N=int(input())
A=list(map(int,input().split()))
def factorization(N):
    temp={}
    while True:
        divided=False
        for i in range(2, int(N**0.5)+1):
            if N%i==0:
                if i in temp:
                    temp[i]+=1
                else:
                    temp[i]=1
                N=N//i
                divided=True
                break
        if not divided:
            temp[1]=1
            if N in temp:
                temp[N]+=1
            else:
                temp[N]=1
            break
    return temp
G={}
for a in A:
    b=factorization(a)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
for a in A:
    x=1
    b=factorization(a)
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
    ans+=x
    ans%=P
print(ans)

Submission status: Time Limit Exceeded

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

LCM = 1
for num in nums:
    LCM = lcm(num, LCM)

# ans = 0
# for num in nums:
#     ans += (LCM // num) % mod
# print(ans % mod)
ans = 0
for num in nums:
    ans += LCM * pow(num, mod - 2, mod)
    ans %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

LCM = 1
for num in nums:
    LCM = lcm(num, LCM)

# ans = 0
# for num in nums:
#     ans += (LCM // num) % mod
# print(ans % mod)
ans = 0
for num in nums:
    ans += LCM * pow(num, mod - 2, mod) % mod


print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def multiple(a, b):
    return a*b // euclid(a, b)
import functools
def lcm(nums):
        return functools.reduce(multiple, nums)%mod
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7
ans =0
for i in range(n):
  ans += lcm(num)*modinv(num[i],mod)
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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


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


n = int(input())
a = list(map(int, input().split(" ")))
alcm = a[0]
for i in a:
    alcm = lcm(alcm, i)

tot = 0
for num in a:
    tot += alcm // num

print(tot % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter, defaultdict
from functools import lru_cache
from itertools import permutations
from heapq import (
    heappush,
    heappop,
    heapreplace,
    heappushpop,
    heapify,
    merge,
    nlargest,
    nsmallest,
)
from statistics import mean, median, mode


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


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


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

clcm = 1
for num in a:
    clcm = lcm(clcm, num)

tot = 0
for num in a:
    tot = (tot + clcm // num) % 1000000007

print(tot)

Submission status: Time Limit Exceeded

Solution code:
def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7

for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
#print(ans)
for i in range(N):
    #print((ans*modinv(A[i],p))%p)
    cnt=(cnt+(ans*modinv(A[i],p))%p)%p
print(cnt%p)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=A[0]
cnt=0
p=(10**9)+7
"""
for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
for i in range(N):
    new[i]=ans//A[i]
#print(ans,new)
for i in range(N):
    cnt=(cnt+new[i])%p
print(cnt)

#print(l)	#これでlistになった
"""
for i in range(N-1):
    ans=(ans*A[i+1])//gcd(ans,A[i+1])
#print(ans)
for i in range(N):
    cnt=(cnt+(ans//A[i])%p)%p
print(cnt%p)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7

for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
for i in range(N):
    new[i]=ans//A[i]
#print(ans,new)
for i in range(N):
    cnt=(cnt+new[i])%p
print(cnt)

#print(l)	#これでlistになった

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7
for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        l.append([keys[j],values[j]])
        #print(insuu)
    #print(l)
    l=[]
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
for i in range(N):
    new[i]=ans//A[i]
#print(ans,new)
for i in range(N):
    cnt=(cnt+new[i])%p
print(cnt)
#print(l)	#これでlistになった

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

ak = [cl.defaultdict(int) for i in range(n)]

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])
        ak[i][j[0]] = j[1]

ans = 0

for i in range(n):
    ui = 1
    for j in pr:
        ui *= pow_k(j,(g[j] - ak[i][j]))
        ui %= mod
    ans += ui
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

ak = [cl.defaultdict(int) for i in range(n)]

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])
        ak[i][j[0]] = j[1]

ans = 0

for i in range(n):
    ui = 1

    for j in pr:
        ui *= pow_k(j,(g[j] - ak[i][j]))
    ans += ui
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x # 指数を割り続け n が 1 に至ったら終了

n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

ak = [cl.defaultdict(int) for i in range(n)]

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])
        ak[i][j[0]] = j[1]

ans = 0

for i in range(n):
    ui = 1

    for j in pr:
        ui *= pow_k(j,(g[j] - ak[i][j]))
    ans += ui
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K = K * x
            x = x ** 2
            n = (n - 1) // 2
        else:
            x = x ** 2
            n = n // 2

    return K * x # 指数を割り続け n が 1 に至ったら終了

n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])

ans = 0

for i in range(n):
    gg = cl.defaultdict(int)
    ui = 1
    ppp = a[i]
    un = prime_decomposition(ppp)
    for j in un:
        gg[j] += 1

    for j in pr:
        ui *= pow_k(j,(g[j] - gg[j]))
    ans += ui
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる


n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])

ans = 0

for i in range(n):
    gg = cl.defaultdict(int)
    ui = 1
    ppp = a[i]
    un = prime_decomposition(ppp)
    for j in un:
        gg[j] += 1

    for j in pr:
        ui *= j ** (g[j] - gg[j])
    ans += ui
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

mod=10**9+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+=(L//A[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
#from math import gcd

def lcm(m, n): return m * n // gcd(m, n)

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

MOD = 10 ** 9 + 7

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

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

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)
    sum = 0
    for a in A:
        sum = (sum + m//a) % MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)
    sum = 0
    for a in A:
        sum = (sum + m//a) % MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)

    def sumup(x, y):
        return (x + m // y) % MOD
    print(reduce(sumup, A, 0))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def main():
    N=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    b=0
    c=1
    for a in A:
        c=c*a//gcd(c,a)
    for a in A:
        b+=(c//a)
        b%=mod
    print(b)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def main():
    N=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    c=A[0]
    for a in A:
        c=c*a//gcd(c,a)
    b=0
    for a in A:
        b+=c//a
        b%=mod
    print(b)
main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)

    def sumup(x, y):
        return (x + m // y) % MOD
    print(reduce(sumup, A, 0))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def fa(n):
    arr = []
    temp = n
    m = int(n**0.5//1)
    for i in range(2, m+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

l = []
for i in range(n):
	deg = fa(a[i])
	if i == 0:
		l = deg
	else:
		for j in range(len(deg)):
			for k in range(len(l)):
				if deg[j][0] == l[k][0]:
					l[k][1] = max(l[k][1], deg[j][1])
					break
			else:
				l.append(deg[j])
lcm = 1
for fac in l:
	factors = pow(fac[0], fac[1], MOD)
	lcm = (lcm*factors)%MOD
ans = 0
for i in range(n):
	ans += pow(a[i], MOD-2, MOD)
print((ans*lcm)%MOD)