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:
from functools import reduce

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

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

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

LCM = reduce(lcm,A)

B = [(LCM//A[i])%mod for i in range(N)]

print(sum(B)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common1 = 1
for a in A[:len(A)// 4]:
    common1 = common1 * a // math.gcd(common1, a)


common2 = 1
for a in A[len(A)// 4: (len(A)// 4) * 2]:
    common2 = common2 * a // math.gcd(common2, a)

common3 = 1
for a in A[(len(A)// 4) * 2: (len(A)// 4) * 3]:
    common3 = common3 * a // math.gcd(common3, a)


common4 = 1
for a in A[(len(A)// 4) * 3 :]:
    common4 = common4 * a // math.gcd(common4, a)


common = common1 * common2 // math.gcd(common1, common2)
common = common * common3 // math.gcd(common, common3)
common = common * common4 // math.gcd(common, common4)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common1 = 1
for a in A[:len(A)// 2]:
    common1 = common1 * a // math.gcd(common1, a)


common2 = 1
for a in A[len(A)// 2:]:
    common2 = common2 * a // math.gcd(common2, a)

common = common1 * common2 // math.gcd(common1, common2)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common = 1
for i in range(len(A)):
    common = common * A[i] // math.gcd(common, A[i])

ans = 0
for i in range(len(A)):
    ans += common // A[i]
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common = 1
for a in A:
    common = common * a // math.gcd(common, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))
s={}
for i in a:
  for j in i:
    if j in s:
      s[j]+=i[j]
    else:
      s[j]=i[j]
b=[]
for i in a:
  b.append(copy(s))
  for j in i:
    b[-1][j]-=i[j]
    if b[-1][j]==0:
      del b[-1][j]
mn=copy(b[0])
for i in b[1:]:
  t=[]
  for j in mn:
    if j in i:
      mn[j]=min(mn[j],i[j])
    else:
      t.append(j)
  for j in t:
    del mn[j]

sm=0
mod=10**9+7
for i in a:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  sm=(sm+pow(r,mod-2,mod))%mod

  
p=1
for i in mn:
  p=(p*pow(i,mn[i],mod))%mod

q=1
for i in s:
  q=(q*pow(i,s[i],mod))%mod

print((q*sm*pow(p,mod-2,mod))%mod)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))
s={}
for i in a:
  for j in i:
    if j in s:
      s[j]+=i[j]
    else:
      s[j]=i[j]
b=[]
for i in a:
  b.append(copy(s))
  for j in i:
    b[-1][j]-=i[j]
    if b[-1][j]==0:
      del b[-1][j]
mn=copy(b[0])
for i in b[1:]:
  t=[]
  for j in mn:
    if j in i:
      mn[j]=min(mn[j],i[j])
    else:
      t.append(j)
  for j in t:
    del mn[j]

s=0
mod=10**9+7
for i in b:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  s=(s+r)%mod

p=1
for i in mn:
  p=(p*pow(i,mn[i],mod))%mod

print((s*pow(p,mod-2,mod))%mod)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    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 a in A:
        ans += l//a
        ans %= mod
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
def main():
    from math 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 a in A:
        ans += (l//a)%mod
        ans %= mod
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
def main():
    from math 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 a in A:
        ans += (l//a)%mod
        ans %= mod
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
def lcm(x,y):return x*y//gcd(x,y)
N = int(input())
a_ls = list(map(int,input().split()))
L = 1
for i in range(N):
    L = lcm(L,a_ls[i])

ans = 0
#print(L)
for i in range(N):
    ans += L//a_ls[i]
    #print(L//a_ls[i])
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
import math

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

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

l = a[0]
for i in range(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:
#!/usr/bin/env python

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

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

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

l = a[0]
for i in range(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:
#!/usr/bin/env python
from functools import *
import math

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

p = 1 
for i in range(n):
    p *= a[i]

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

l = a[0]
for i in range(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:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = Counter([])
    for k,v in factors[i].items():
        if k not in l:
            l[k] = v
        elif l[k] < v:
            l[k] = v

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v,mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    for k,v in diff.items():
        if k not in l:
            l[k] = 0
        l[k] += v

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v,mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math 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 a in A:
    ans += (l//a)%mod
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    l += diff

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v,mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    ceil = int(a**0.5)+1
    for d in range(2,ceil):
        for _ in range(100):
            if a%d==0:
                a//=d
                tmp.append(d)
            else:
                break
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    l += diff

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v)
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
と思ったけど、普通に最小公倍数を求めると、値が大きくなりすぎて処理できない。
なので、積は求めずに、素因数の足し引きだけ処理する。
"""
from math import gcd
from collections import Counter
mod = 10**9 +7
N = int(input())
A = list(map(int,input().split()))
factors = []
for i in range(N):
    a = A[i]
    tmp = []
    d = 2
    while d * d <= a:
        while a%d==0:
            a//=d
            tmp.append(d)
        d += 1
    if a != 1:
        tmp.append(a)
    factors.append(Counter(tmp))
    if i == 0:
        l = Counter(tmp)

for i in range(1,N):
    diff = factors[i]-l
    l += diff

ans = 0
for factor in factors:
    diff = l - factor
    tmp = 1
    for k,v in diff.items():
        tmp *= pow(k,v)
    ans += tmp
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math 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 a in A:
    ans += l//a
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import functools
import operator


def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = [Counter(prime_factor(a, temp)) for a in A]
    lcm = functools.reduce(operator.ior, ap_list, Counter())

    mod = 10 ** 9 + 7
    ans = 0
    for ap in ap_list:
        b = 1
        for v in (lcm - ap).elements():
            b *= v
            if b > mod:
                b %= mod
        ans += b
        if ans > mod:
            ans %= mod

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import functools
from math import gcd


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


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))
    a_lcm = lcm(A)

    mod = 10 ** 9 + 7

    ans = 0
    for a in A:
        ans += a_lcm // a
        if ans > mod:
            ans %= mod
            
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import functools
import operator

def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]

def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = [Counter(prime_factor(a, temp)) for a in A]
    lcm = functools.reduce(operator.or_, ap_list)

    mod = 10 ** 9 + 7
    ans = 0
    for ap in ap_list:
        b = 1
        for k, v in (lcm - ap).items():
            for _ in range(v):
                b *= k
                if b > mod:
                    b %= mod
        ans += b
        if ans > mod:
            ans %= mod

            
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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 gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

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

L = A[0]
for a in A:
    L = lcm(L, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import functools
from math import gcd


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


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))
    a_lcm = lcm(A)

    mod = 10 ** 9 + 7

    ans = 0
    for a in A:
        ans += a_lcm // a
        if ans > mod:
            ans %= mod
            
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
import functools
from math import gcd


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


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))
    a_lcm = lcm(A)

    mod = 10 ** 9 + 7

    ans = 0
    for a in A:
        ans += a_lcm // a
        ans %= mod
            
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        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()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = (ans+gcd//a)%m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = (ans+gcd//a)%m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
P = 10**9 + 7

import math
import numpy as np

primes = []
check = [True] * (10**3 + 1)
for p in range(2, 10**3):
    if check[p] == True:
        primes.append(p)
        for j in range(2, 10**3 // p + 1):
            check[p * j] = False

def pf(A):
    e = [0] * 10**6
    for p in primes:
        while A % p == 0:
            A = A // p
            e[p] += 1
    
    if A != 1:
        e[A] = 1
        primes.append(A)

    return e

def modpow(a, n, P):
    if n == 1:
        ans = a % P
    else:
        if n % 2 == 0:
            ans = (modpow(a, n // 2, P) ** 2) % P
        else: # n % 2 == 1
            ans = (a * (modpow(a, n // 2, P) ** 2)) % P

    return ans

N = int(input())
A = [int(x) for x in input().split()]
E = [pf(A[i]) for i in range(N)]

L = [0] * 10**6
for p in primes:
    L[p] = max(E[i][p] for i in range(N))

M = 1
for p in primes:
    M = (M * p**L[p]) % P

ans = 0
for i in range(N):
    ans = (ans + M * modpow(A[i], P - 2, P)) % P

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
M = 10 ** 6 + 1
num = [0 for i in range(M)]
num[0] = 1
for i in range(M):
  if num[i] == 0:
    if i + 1 > sqrt(M):
      break
    n = 2 * (i + 1)
    while n <= M:
      num[n-1] = 1
      n += (i+1)
primes = [i + 1 for i in range(M) if num[i] == 0]
D = [{} for i in range(N)]
LCM = {}
for j in range(N):
  i = 0
  while A[j] > 1:
    c = 0
    while A[j] % primes[i] == 0:
      c += 1
      A[j] //= primes[i]
    if c:
      D[j][primes[i]] = c
      LCM[primes[i]] = max(c, LCM.get(primes[i], 0))
    i += 1
ans = 0
for j in range(N):
  add = 1
  for k in LCM.keys():
    add = (add * (k ** (LCM[k] - D[j].get(k, 0)) % mod)) % mod
  ans = (ans + add) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
D = [{} for i in range(N)]
LCM = {}
for j in range(N):
  i = 2
  while A[j] > 1:
    c = 0
    while A[j] % i == 0:
      c += 1
      A[j] //= i
    if c:
      D[j][i] = c
      LCM[i] = max(c, LCM.get(i, 0))
    i += 1
ans = 0
for j in range(N):
  add = 1
  for k in LCM.keys():
    add = (add * (k ** (LCM[k] - D[j].get(k, 0)) % mod)) % mod
  ans = (ans + add) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
D = [{} for i in range(N)]
LCM = {}
for j in range(N):
  i = 2
  while A[j] > 1:
    c = 0
    while A[j] % i == 0:
      c += 1
      A[j] //= i
    if c:
      D[j][i] = c
      LCM[i] = max(c, LCM.get(i, 0))
    i += 1
ans = 0
for j in range(N):
  add = 1
  for k in LCM.keys():
    add = (add * (k ** (LCM[k] - D[j].get(k, 0)))) % mod
  ans = (ans + add) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

mod = 10**9+7

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

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

ans = 0
for a in A:
  ans += LCM // a
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce


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


def lcm(l):
    return reduce(lcm_base, l, 1)


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)%mod
        ans %= mod

    print(ans % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
import sys
input = sys.stdin.readline

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


# Load data
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
# LCM: dict 最小公倍数の素因数分解
LCM = 1
for a in A:
    LCM = lcm(LCM, a)
# A2Factor: list A[i]の素因数分解
A2Factor = []

ans = 0
for a in A:
    ans += (LCM//a)%mod
    ans %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
import sys
input = sys.stdin.readline
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    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]]
    PRIME_LIST = primes(max(A))
    def factorization(n):
        arr = []
        temp = n
        for i in PRIME_LIST:
            if temp%i==0:
                # cnt=0
                while temp%i==0:
                    # cnt+=1
                    temp //= i
                    arr.append(i)

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

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

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        arr = Counter(arr)
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter
import sys
input = sys.stdin.readline
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    
    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)

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

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

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        arr = Counter(arr)
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()