Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr
n = int(input())
a = list(map(int, input().split()))
cur = a[0]
ans = 0
for item in a:
  cur2 = cur*item//fr.gcd(cur, item)
  ans = (ans*cur2//cur + cur2//item)%(10**9+7)
  cur = cur2
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
#A = [1000000 - x for x in range(N)]
A = list(map(int, input().split()))

LCM = 1
for i in A:
    LCM = i * LCM // gcd(LCM, i)

ans = 0
for i in A:
    ans = (ans + LCM // i) % 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ABC152e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    MOD = 10**9+7

    from fractions import gcd

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

    ans = a[0]

    b = 1
    l = ans

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

    for i in range(1, n):
        ans = ans * a[i] // gcd(ans, a[i])
        b *= (ans // l)
        # print(b)
        b += ans // a[i]
        b %= MOD
        #print(a[i], b, ans, l)
        l = ans
    # print(ans)
    o = ans
    # print(o)

    # for i in a:
    #    b += o//i % MOD
    print(b % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions as math
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    t=1
    for i in numbers:
      t=lcm_base(t,i)
    return t
N=int(input())
A=list(map(int,input().split()))
tmp=lcm_list(set(A))
ans=0
for i in A:
  ans+=tmp//i
  ans%=(10**9+7)
print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions

def lcms(a):
    ans = a[0]
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])
    return ans


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

lcm_a = lcms(A)

sum_b = 0
for a in A:
    sum_b = (sum_b + lcm_a // a) % (10**9+7)

print(sum_b)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
import numpy as np
A = np.array(A, np.int64)
A = lcm // A
A %= mod
ans += np.sum(A)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000003
  
mod = 1000000007
  
prime = [0 for i in range(MAX)] 
  
max_map = dict() 
  
# function to return a^n 
def power(a, n): 
      
    if n == 0: 
        return 1
    p = power(a, n // 2) % mod 
    p = (p * p) % mod 
      
    if n & 1: 
        p = (p * a) % mod 
    return p 
  
# function to find the smallest prime 
# factors of numbers upto MAX 
def sieve(): 
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX): 
        if prime[i] == 0: 
            for j in range(i * 2, MAX, i): 
                if prime[j] == 0: 
                    prime[j] = i 
            prime[i] = i 
  
# function to return the LCM modulo M 
def lcmModuloM(arr, n): 
      
    for i in range(n): 
        num = arr[i] 
          
        temp = dict() 
          
        # temp stores mapping of prime factors  
        # to its power for the current element 
        while num > 1: 
               
            # factor is the smallest prime 
            # factor of num 
            factor = prime[num] 
              
            # Increase count of factor in temp 
            if factor in temp.keys(): 
                temp[factor] += 1
            else: 
                temp[factor] = 1
                  
            # Reduce num by its prime factor 
            num = num // factor 
              
        for i in temp: 
            # store the higest power of every prime 
            # found till now in a new map max_map 
            if i in max_map.keys(): 
                max_map[i] = max(max_map[i], temp[i]) 
            else: 
                max_map[i] = temp[i] 
              
    ans = 1
      
    for i in max_map: 
          
        # LCM is product of primes to their 
        # higest powers modulo M 
        ans = (ans * power(i, max_map[i])) 
    return ans 

n = int(input())
a = input().split()
a = [int(i) for i in a]

sieve()
lcm = lcmModuloM(a, n)

count = 0

for i in a:
    count += (lcm // i)

print (count % 1000000007)

Submission status: Time Limit Exceeded

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

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


def cal_lcm(a, b):
  return int(a*b//gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = (ans*(lcm_//lcm) + (lcm_//a_list[i]) )% MOD
  lcm = lcm_

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N=input()
I=input()
a=I.split()
a.sort(reverse=True)
s=0
x=int(a[0])
for i in range(len(a)-1):
    b=int(a[i+1])
    z=x*b
    if(x<b):
        tmp=x
        x=b
        b=tmp
    r=x%b
    while r!=0:
        x=b
        b=r
        r=x%b
    x=z/b
u=[]
c=0
l=0
o=int(math.sqrt(x))
pivot=sum(1 for y in a if int(y)>=o)
pivot=pivot-1
l = 0
for j in range(len(a)):
    if(j>=pivot):
        c=0
        for k in reversed(range(0,l)):
            if(a[j]==u[k]):
                s=s+u[k]
                l=k
                c=1
                break
        if(c==0):
            s=s+x/int(a[j])
    else:
        u.append(x/int(a[j]))
        s=s+int(u[j])
        l=l+1
print(int(s)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import fractions
from functools import reduce
n = int(input())
A = []
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)
Z = lcm(*A)
ans = sum(Z//a%mod for a in A)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
bbn=1000000007
	
#+++++

def modinv(a,m):
	b=m
	u=1
	v=0
	
	while b > 0:
		t = a //b
		a = a - (t * b)
		a,b = b,a
		u = u - (t * v)
		u,v=v,u
	
	u = u % m
	if u < 0:
		u+=m
	return u

def gcd(a,b):
	while b!= 0:
		a,b=b,a%b
		
	return a
		
def main():
	n = int(input())
	al = list(map(int, input().split()))
	
	#saisyoukoubausuu
	ss=1
	for v in al:
		ss = ss*v//gcd(ss,v) 
		#ss %= bbn
	
	ret=0
	for v in al:
		ret+=(ss * modinv(v,bbn))
		ret%=bbn
		
	
	print(ret)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

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

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b % mod

ans = t % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

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

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

# print('input >>')
N = int(input())
A = list(map(int,(input().split())))

lcmn = lcm(A)

ans = 0
for A_ in A:
    ans += (lcmn // A_) % mod

# print('-----output-----')
print(int(ans%mod))

Submission status: Time Limit Exceeded

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

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
		
def lcm(a, b):
	return a * b // gcd(a, b)
		
		
a = 1
for i in range(N):
	a = lcm(A[i], a)
ans = 0
	
for i in range(N):
	ans += (a // A[i]) % MOD
	ans %= MOD
	
print(int(ans))

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# 最大公約数
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)

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

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

sums = 0
for i in range(N):
    sums += x // A[i]
    sums %= 10 ** 9 + 7

print(sums)

Submission status: Time Limit Exceeded

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

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

import functools

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)
def lcm(nums):
        return functools.reduce(multiple, nums)


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:


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

def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        newl = []
        ind = 0
        while True:
            if ind + 1 < len(arr):
                newl.append(lcm_core(arr[ind],arr[ind+1]))
                ind += 2
            else:
                newl.append(arr[ind])
                ind += 1
            if ind >= len(arr):
                break
        return lcm(newl)


n = int(input())

if n == 1:
    print(1)
else:
    arr = list(map(int,input().split()))
    l = lcm(arr)
    m = 10**9+7
    l,mcnt = l%m,l//m
    ans = 0
    for i in range(n):
        temp1 = l // arr[i] + (m // arr[i]) * mcnt
        temp2 = l % arr[i] + (m % arr[i]) * mcnt
        temp2 = temp2 // arr[i]
        ans += temp1 + temp2
        ans %= m
    ans %= m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
g = 1
res = 0
for i in a:
    g = i*g//fractions.gcd(i,g)
for i in range(n):
    res += g//a[i]
    res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000000+7
def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)

n = int(input())
dat = list(map(int, input().split()))
dat.sort()
dat2 = []

base = 1
for i in range(len(dat)):
    base = lcm(base, dat[i])
res = 0

for i in range(len(dat)):
    res += base // dat[i]
    res %= MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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 = (m * x) // gcd(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:
MOD = 1000000000+7
def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)

n = int(input())
dat = list(map(int, input().split()))
dat.sort(reverse=True)
dat2 = []

base = 1
for i in range(len(dat)):
    base = lcm(base, dat[i])
res = 0

for i in range(len(dat)):
    res += base // dat[i]
    res %= MOD

print(res)

Submission status: Time Limit Exceeded

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

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

N=int(input())
A=list(map(int,input().split()))
a_lcm=A[0]

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

result=0
for i in range(N):
    result+=a_lcm//A[i]
    result%=1000000007
print(result%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

for i in range(N):
    res += l//A[i]

print(res % 1000000007)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
import fractions

sys.setrecursionlimit(100000)

res = 1e9 + 7

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

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

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

# lcm_num = lcm_list(As)

sum = 0.0

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

print(int(sum % res))

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    while a%b:
        if(a%b!=0):
            k=b
            b=a%b
            a=k
        else:
            return b
    return b
buf=[]
mul=1

n=int(input())
i=0;
for x in input().split():
    buf.append(int(x))  
    mul=mul*(buf[i]/gcd(mul,buf[i]))
    i+=1
sum=0
for i in range(n):
    buf[i]=mul/buf[i]
    sum+=buf[i]
    sum%=1000000007
print(int(sum))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from functools import reduce

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

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

    mod = 10 ** 9 + 7

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

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + L * pow(x, mod - 2, mod)) % mod
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
import numpy as np
A = np.array(A, np.int64)
ans += np.sum(lcm // A)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
MOD = 10**9+7
#-------------------------------------------------------------------
#gcd (最大公約数)(greatest common divisor)
#-------------------------------------------------------------------
# Python3.4以前なら、
from fractions import gcd
import fractions
from functools import reduce
#-------------------------------------------------------------------
#lcm (最小公倍数)
#-------------------------------------------------------------------
def lcm_base(a, b):
	return (a * b) // gcd(a, b)

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

def lcm_list(nums):
	return lcm(*nums)
#-------------------------------------------------------------------

n = int(input())

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

from itertools import groupby

#「groupby」を使って、
L = [[k, len(list(g))] for k, g in groupby(A)]

#p( L )
#	#[[12, 5]]
#	#[[999998, 1], [999999, 1], [1000000, 1]]

x=1
for k,g in L:
	x = lcm_base(x,k)

ans=0
for k,g in L:
	b = x // k
	ans+=(b*g) % MOD


print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2] != 1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]
def mod_inv(a,mod):
    x = extgcd(a,mod)[0]
    return (mod + x % mod)% mod
def comb(n,k,mod):
    c = 1
    for i in range(k):
        c = c*(n-i)%mod
        c = c*mod_inv(i+1,mod)%mod
    return c
n = int(input())
a = list(map(int,input().split()))
g = 1
mod = 10**9 + 7
for i in range(n):
    g = g*a[i]//fractions.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:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
x = reduce(lambda x, y: x * y // gcd(x, y), a)

print(sum([(x // ai) % MOD for ai in a]) % MOD)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    from fractions import gcd

    def lcd(x, y):
        g = gcd(x, y)
        return x * y // g

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

    l = 1
    for e in a:
        l = lcd(l, e)

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000000+7
def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)
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

n = int(input())
dat = list(map(int, input().split()))
dat2 = []

base = 1
for i in range(len(dat)):
    base = lcm(base, dat[i])
res = 0
for i in range(len(dat)):
    res += base // dat[i]
    res %= MOD

#print(base)
print(res)

Submission status: Time Limit Exceeded

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

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


def cal_lcm(a, b):
  return int(a*b//gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = ans*(lcm_//lcm) % MOD
  ans = (ans + (lcm_//a_list[i])) % MOD
  lcm = lcm_

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys

sys.setrecursionlimit(10000000)

res = 1e9 + 7

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

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

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

# lcm_num = lcm_list(As)

sum = 0.0

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

print(int(sum % res))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

d = defaultdict(int)

pf = []
for a in A:
    res = []
    for i in range(2, int(a ** 0.5) + 1):
        if a % i == 0:
            cnt = 0
            while a % i == 0:
                cnt += 1
                a //= i
            d[i] = max(d[i], cnt)
            res.append((i, cnt))
    if a != 1:
        d[a] = max(d[a], 1)
        res.append((a, 1))
    pf.append(res)

ans = 0
for i, a in enumerate(A):
    tmpD = d.copy()
    for k, v in pf[i]:
        tmpD[k] -= v
    b = 1
    for k, v in tmpD.items():
        if v <= 0:
            continue
        b *= pow(k, v, mod)
        v %= mod
    ans += b
    ans %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#n,m = [int(i) for i in readline().split()]
#d = [int(i) for i in readline().split()]
MOD = 10**9+7

n = int(input())
a = [int(i) for i in readline().split()]

from fractions import gcd
m = a[0]
for i in a:
    m = i//gcd(m,i)*m

ans = 0
for i in a:
    ans += (m//i)%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
n=int(input())
a = list(map(int,input().split()))   
lcm = a[0]
for i in a[1:]:
  lcm = lcm*i/gcd(lcm, i)

for i in range(len(a)):
  a[i]=int(lcm/a[i])
print(sum(a)% (pow(10,9)+7))

Submission status: Time Limit Exceeded

Solution code:
def gcd(u, v):
    k = 0
    while((0 == (u & 1)) and (0 == (v & 1))):
        k += 1
        u >>= 1
        v >>= 1

    if ((u & 1) == 0) :
        t = u >> 1
    else:
        t = -v
    while ((t & 1) == 0):
        t >>= 1
    if (t > 0) :
        u = t
    else :
        v = -t

    while (0 != t):
        # /* tが偶数である限り、2で割り続ける */
        while ((t & 1) == 0):
            t >>= 1
        if (t > 0) :
            u = t
        else :
            v = -t

        t = u - v
    return u * (1 << k)

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])
mod = 10**9+7

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort(reverse=True)
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += (first * x // A[i]) % MOD

print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
c = 1


def lcm(a, b):
    h, l = max(a, b), min(a, b)
    while l != 0:
        h, l = l, h % l
    return a * b // h


for i in range(N):
    if c % A[i] != 0:
        c = lcm(c, A[i])
M = 10 ** 9 + 7
ans = 0
for a in A:
    ans += (c // a) % M
print(ans % M)

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

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

  print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
def lcm_for_list(numbers):
    from functools import reduce
    return reduce(lcm, numbers, 1)
 
def lcm(x, y):
    from fractions import gcd  # for Ver.3.4 or lower.
    return (x * y) // gcd(x, y)

if __name__ == "__main__":
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    ll = lcm_for_list(A)
    print(sum(list(map(lambda a: (ll//a)%mod, A)))%mod)

Submission status: Time Limit Exceeded

Solution code:
def gcm(a: int, b: int):
    while b > 0:
        a, b = b, a % b
    return a


def lcm(a: int, b: int):
    return a * b // gcm(a, b)


n = int(input())
a_array = list(map(int, input().split()))
a_lcm = 1
for a in a_array:
    a_lcm = lcm(a_lcm, a)
count = 0
for a in a_array:
    count += (a_lcm // a) % (10 ** 9 + 7)
    count %= 10 ** 9 + 7
print(count)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

if N==1:
  print(1)
else:
  alist.sort()
  lcm_alist=lcm_list(alist)
  
  answer=0
  last_a=-1
  last_b=-1
  for a in alist:
    b=last_b
    if a!=last_a:
      b=lcm_alist//a
      last_a=a
      last_b=b

    answer=(answer+b)%(10**9+7)
    
  #print(blist)
  print(answer)

Submission status: Time Limit Exceeded

Solution code:


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

def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        newl = []
        ind = 0
        while True:
            if ind + 1 < len(arr):
                newl.append(lcm_core(arr[ind],arr[ind+1]))
                ind += 2
            else:
                newl.append(arr[ind])
                ind += 1
            if ind >= len(arr):
                break
        return lcm(newl)


n = int(input())

if n == 1:
    print(1)
else:
    arr = list(map(int,input().split()))
    l = lcm(arr)
    m = 10**9+7
    l,mcnt = l%m,l//m
    # print(l)
    # buf = []
    # for i in range(n):
    #     buf.append(l/arr[i])
    # print(buf)
    ans = 0
    for i in range(n):
        temp1 = l // arr[i] + (m // arr[i]) * mcnt
        temp2 = l % arr[i] + (m % arr[i]) * mcnt
        # print(temp2%arr[i])
        temp2 = temp2 // arr[i]
        ans += temp1 + temp2
        ans %= m
    ans %= m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  a_ = tuple(set(a))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      ln = len(a)
      for i in range(1, ln):
          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:
n = int(input())
an = list(map(int, input().split()))

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

MOD = 10 ** 9 + 7
l = lcm(an)
sm = 0
bn = []
for a in an:
  bn.append((l // a) % MOD)
for b in bn:
  sm = (sm + b) % MOD
print(sm)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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 = l * a // fractions.gcd(l, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

import copy
N = int(input())
Ps = list(map(int,input().split(" ")))
org_Ps = copy.deepcopy(Ps)
prime_nums = primes(10 ** 5)

Ps.sort()
mul = 1
used = False
for p in prime_nums:
    used = False
    for i in range(len(Ps)):
        if Ps[i] %p == 0:
            Ps[i]//=p
            if not used:
                used = True
                mul *= p

MOD = 10 ** 9 + 7
g = 1

for p in Ps:
    g = g* p // fractions.gcd(g, p)
g *= mul
ans = 0

for p in org_Ps:
    ans += g//p
    ans %= MOD
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

A.sort(reverse=True)

l = 1
for i in A:
  if l % i != 0:
    l = lcm(l, i)

num = [0] * (10 ** 6 + 1)

ans = 0
for i in A:
  if num[i] == 0:
    v = (l // i) % MOD 
    num[i] = v
  else:
    v = num[i]
  ans = (ans + v) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
MOD = 10**9+7
#-------------------------------------------------------------------
#gcd (最大公約数)(greatest common divisor)
#-------------------------------------------------------------------
# Python3.4以前なら、
from fractions import gcd
import fractions
from functools import reduce
#-------------------------------------------------------------------
#lcm (最小公倍数)
#-------------------------------------------------------------------
def lcm_base(a, b):
	return (a * b) // gcd(a, b)

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

def lcm_list(nums):
	return lcm(*nums)
#-------------------------------------------------------------------

n = int(input())

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

from itertools import groupby

#「groupby」を使って、
L = [[k, len(list(g))] for k, g in groupby(A)]

#p( L )
#	#[[12, 5]]
#	#[[999998, 1], [999999, 1], [1000000, 1]]

x=1
for k,g in L:
	x = lcm_base(x,k)

ans=0
for k,g in L:
	b = x // k
	ans+=(b*g)
	ans = ans % MOD


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
import fractions
from functools import reduce

n=int(input())
c = 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)

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

v=lcm(*c)
ans=0

for i in range(n):
    ans+=v//c[i]
    ans%=mod
print(ans)