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 fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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

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

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    for a in A:
        ans += D // a
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
from collections import Counter


def least_common_multiple(iter):
    '''
    最小公倍数を返す
    '''
    lcm = lambda x, y: x*y//gcd(x, y)
    return reduce(lcm, iter)


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
l = least_common_multiple(list(c.keys()))
ans = 0
MOD = 10**9+7
for k, v in c.items():
    ans = (ans + (l // k * v) % MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np
MOD = 10**9+7
 
def lcm_n(l):
    rtn = l[0]
    for i in range(1,N):
        rtn = rtn * l[i] // fractions.gcd(rtn,l[i])
    return rtn
  
N = int(input())
lA = list(map(int,input().split()))
A = np.array(lA,dtype = np.int64)
lcm = lcm_n(lA)

A = (lcm // A) % MOD
 
print(sum(A) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from time import*
from fractions import*
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    s=lcm(s,t)
    if time()-start>.7:
        s=max(a)
        break
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

Submission status: Time Limit Exceeded

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

lcm = 1
mod = 10**9+7

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

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

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

lcm = 1
for f in d.keys():
    lcm *= f ** d[f]

ans = (lcm * cnt_1)%mod
# 1のかず
for factors in factors_list:
    cnt = 1
    for f in d.keys():
       cnt *= f ** (d[f]-factors[f])
       cnt %= mod
    ans += cnt
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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


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


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

y = lcm_list(A)
MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += y // a
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    return gcd(d,s%d) if d!=0 else s 
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    ans+=(f//iu)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import fractions
from functools import reduce

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


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


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


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions

N = int(input())
A = list(map(int,input().split()))
A0 = min(A)
B0 = A0
if N == 1:
    ans = 1
else:
    for a in A:
        B0 = (B0 * a) // fractions.gcd(B0,a)
    B0 = B0//A0
    ans = 0
    for a in A:
        ans += (A0*B0//a)
        ans = ans % (10**9 + 7)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

div = 10**9+7

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

import fractions
ans = A[0]
for a in A[1:]:
    ans = ans * a // fractions.gcd(ans, a)

sum_b = 0
for a in A:
    sum_b += ans // a % div

print(sum_b % div)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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

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

    return True

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

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

n = I()
a = LI()
l = 1
for i in a:
    l = lcm(l,i)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
ans = 0
b = []
n = int(input())
a = list(map(int,input().split()))
kari = a[0]
for i in a:
    kari = lcm(kari,i)
for i in a:
    ans+=(kari//i)
    ans = ans%1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,fractions
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

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

G = l[0]
for i in range(N-1,0,-1):
    G = fractions.gcd(G,l[i])
    if G==1:
        break
gcd = G
L = [l[i]//gcd for i in range(N)]
lcm = lcm_list(L)

# print(lcm,gcd,'aaa')
ANS = 0
for i in range(N):
    elm = L[i]
    ANS += (lcm//elm)
    ANS %= u
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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

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

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

def main():
    N = int(input())
    A = list(map(int, input().split()))
    D = lcm_list(A)
    ans = 0
    MOD = 10 ** 9 + 7
    for i in range(N):
        ans += D // A[i]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline


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

N=int(input())
a=list(map(int,input().split()))
calc=(lcm(a))  # 実行結果: 12

ans=0
for index,item in enumerate(a):
    ans+=(calc)//item
    ans%=(10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import numpy as np

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)

As = np.array(As)
lc = np.array([lcm]*n)

print(np.sum(lc//As) % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
lcm = 1
for i in range(n):
  if lcm % a[i] == 0:
    continue
  lcm = lcm * a[i] / gcd(lcm, a[i])
for i in range(n):
  cnt += lcm / a[i]
  cnt %= 10**9+7
print(int(cnt))

Submission status: Time Limit Exceeded

Solution code:
# 最小公倍数を目指す？
n = int(input())
arr = list(map(int, input().split()))


def gcd(a, b):
    if a < b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return b % (10 ** 9 + 7)


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


a = arr[0]
for i in range(1, n):
    a = lcm(a, arr[i])
ans = 0
for av in arr:
    z = (a // av) % (10 ** 9 + 7)
    ans += z
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:

import fractions as ft
#import math as ft


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // ft.gcd(a,lcm_)
#    print(lcm_)
    
ans = 0
bn = [0]*n
for i, a in enumerate(an):
    t = lcm_//a
    ans += t 
    ans %= prime

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod
    

def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
def main():

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

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

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

    B = set()
    ps = set()
    for i in range(N):
        if isprime(A[i]):
            ps.add(A[i])
        else:
            B.add(A[i])
    B = sorted(list(B))

    b = 1
    for i in range(len(B)):
        if b % B[i] != 0:
            g = gcd(b, B[i])
            b = b * B[i] // g

    for p in ps:
        if b % p != 0:
            b *= p
            
    ans = 0
    for i in range(len(A)):
        ans += (b // A[i]) % mod
        ans %= mod
    return ans

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
def lcm(a, b):
    return (a * b) // gcd(a, b)
m = 1
for x in a:
    m = lcm(m, x)
# print(m)
MOD = 1000000007
ans = 0
for x in a:
    b = m // x
    ans = (ans + b) % MOD
print(math.floor(ans))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

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

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

dev = 10 ** 9 + 7
ans = 0
for i in range(N):
    ans += (lcm // A[i]) % dev
    ans %= dev
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
import functools
INF = float("inf")

MOD = 1000000007  # type: int


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


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


def solve(N: int, A: "List[int]"):

    ans = 0
    # 最小公倍数
    lcm = 1
    for a in A:
        d, m = divmod(lcm, a)
        if m == 0:
            ans += d
            ans %= MOD
        else:
            ss = LCM(lcm, a)
            ans *= ss//lcm
            ans %= MOD
            lcm = ss
            ans += lcm//a
            ans %= MOD
    print(ans % MOD)

    return


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 functools import reduce, lru_cache


@lru_cache(maxsize=2**22)
def GCD(x, y):
    if y == 0:
        return x
    else:
        return GCD(y, x % y)


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


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a,N):
      from fractions import gcd
      x = a[0]
      for i in range(1, N):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  z=lcm(A,N)
  MOD=10**9+7
  ans=0
  for i in range(N):
    ans+=z//A[i]%MOD
  print(ans%MOD)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from time import*
from fractions import*
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    if time()-start>.7:
        s=max(a)
        break
    else:
        s=lcm(s,t)
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
memo = dict()


def gcd(a, b):
    if (a, b) in memo:
        return memo[(a, b)]

    while b != 0:
        a, b = b, a - (a // b) * b

    memo[(a, b)] = a
    memo[(b, a)] = a

    return a


def lcm(iterable):
    a = iterable[0]

    for b in iterable:
        a = a * b // gcd(a, b)

    return a


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

    lcm_an = lcm(an)

    ans = 0
    for a in an:
        ans += lcm_an // a
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import numpy as np
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
lst = list(map(int, input().split()))

koubai = lcm_list(lst)
tmp = np.array([koubai for _ in range(n)])
tmp2 = tmp//lst
print(tmp2.sum() % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

x = 1
for i in range(1, n):
    p = a[i] // gcd(a[0], a[i])
    x = p * x // gcd(p, x)

res = x
for i in range(1, n):
    y = a[0] * x // a[i]
    res += y

print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(4100000)
    input = sys.stdin.readline
    from fractions import gcd
    from collections import Counter

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

    # A を圧縮
    c = Counter(A)
    values_counts = c.most_common()

    L = values_counts[0][0]
    for vc in values_counts[1:]:
        L = L * vc[0] // gcd(L, vc[0])

    ans = 0
    for vc in values_counts:
        ans += (L // vc[0]) * vc[1]
        ans %= INF
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

def lcm_base(x, y):
    mod = 10**9 + 7
    return (x * y) // fractions.gcd(x, y) 

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

N = int(input())

mod = 10**9 + 7

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

num = lcm_list(A)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
#N = 10**4
#A = [i for i in range(10**6, 10**6-N, -1)]

L = 1

for Ai in A:
    L = lcm(L, Ai)

ans = 0

for Ai in A:
    ans += L//Ai
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys

def main():
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

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

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

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
def main():

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

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

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

    B = set()
    ps = set()
    for i in range(N):
        if isprime(A[i]):
            ps.add(A[i])
        else:
            B.add(A[i])
    B = sorted(list(B))

    b = 1
    for i in range(len(B)):
        if b % B[i] != 0:
            g = gcd(b, B[i])
            b = b * B[i] // g

    for p in ps:
        if b % p != 0:
            b *= p
            
    ans = 0
    for i in range(len(A)):
        ans += (b // A[i]) % mod
        ans %= mod
    return ans

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

Submission status: Time Limit Exceeded

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


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


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

l = A[0]
for a in A:
  if l%a != 0:
    l = lcm(l, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
import math
import collections
def input():
    return sys.stdin.readline()[:-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    # li=[0]*(max(a)+1)
    dic={}
    for i in range(n):
        tmp=collections.Counter(prime_factor(a[i]))
        # print(tmp)
        for j in list(tmp.keys()):
            if not j in dic:
                dic[j]=tmp[j]
            else:
                dic[j]=max(dic[j],tmp[j])
    ans=1
    # print(dic)
    for i in dic.keys():
        # print(dic[i],i)
        ans*=i**dic[i]
    # print(ans)
    cnt=0
    for i in range(n):
        cnt+=ans//a[i]
        cnt%=mod
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


def multiple(a, b):
    return a*b // xgcd(a, b)

def lcm(nums):
        return functools.reduce(multiple, nums)

n = int(input())
a = [int(i) for i in input().split(" ")]
c = 10**9 + 7
lcm_ = lcm(a)
ans = 0
for i in a:
    ans += lcm_//i % c
print(ans%c)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7

N = int(input())
A = list(map(int,input().split()))
fact = [1]*(10**7+10)
rfact = [1]*(10**7+10)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

value = lcm_list(A)
ans = 0
for i in range(N):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# 最小公倍数を目指す？
n = int(input())
arr = list(map(int, input().split()))


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


def lcm(a, b):
    ret = (a * b) // gcd(a, b)
    # ret %= 10 ** 9 + 7 これがめっちゃ怖い TLEなりそう..
    return ret


a = arr[0]
for i in range(1, n):
    a = lcm(a, arr[i])
ans = 0
for av in arr:
    z = (a // av) % (10 ** 9 + 7)
    ans += z
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

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

n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g

for x in a:
  ans+=(l//x)%m

print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
from functools import reduce

res = 1e9 + 7


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

ans = int(As[0] % res)
for i in range(1, N):
     ans = ans // (fractions.gcd(ans, As[i]) % res) * As[i]

# lcm_num = lcm_list(As)

sum = 0

for i in range(N):
  sum += int((ans / As[i]) % res)

print(int(sum % res))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
sum_b=0
for ai in a:
    bi=a_lcm//ai
    b.append(bi)
    sum_b+=bi
print(sum_b%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input().strip())
A = [int(s) for s in input().strip().split()]
M = 10 ** 9 + 7

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

factors = Counter()
for a in A:
    d = Counter()
    while a % 2 == 0:
        d[2] += 1
        a //= 2
    for i in range(3, int(a ** 0.5) + 1, 2):
        while a % i == 0:
            d[i] += 1
            a //= i
        if a == 1:
            break
    if a > 1:
        d[a] += 1
    factors |= d
# print(factors)
m = 1
for k, v in factors.items():
    m = (m * pow(k, v, M)) % M

result = 0
for a in A:
    result = (result + m * modinv(a, M)) % M
print(result)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

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

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    a = v[0]
    lcm = v[0]
    for i in range(n):
        if i > 0:
            tmp = a
            a = gcd(a, v[i])
            c_lcm = tmp * v[i] // a
            # print("lcm: ", lcm)
            # print("clcm: ", c_lcm)
            lcm = c_lcm * lcm // gcd(c_lcm, lcm)
    ans = 0
    for i in range(n):
        ans += lcm // v[i]
    print(ans % (10**9+7))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from time import*
from fractions import*
start=time()
M=10**9+7
lcm=lambda x,y:x//gcd(x,y)*y
n,*a=map(int,open(0).read().split())
if n==1:
    print(1)
    exit()
s=a[0]
for t in a[1:]:
    if time()-start>1:
        s=max(a)
        break
    else:
        s=lcm(s,t)
c=0
for i in a:
    c+=s//i
    c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
input = sys.stdin.readline

# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

n = int(input())
a = list(map(int, input().split()))
a_tmp = list(set(sorted(a, reverse=True)))
lcm_ = a_tmp[0]
for i in a_tmp:
    lcm_ = lcm(lcm_, i)

b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)