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:
def gcd(a,b):
    if (b==0):
        return a
    else:
        return gcd(b, a%b)


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

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

ans = 0
for i in a:
    ans += (LCM // i)

ans %= mod
print(ans)

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(*numbers):
    return reduce(lcm_base, numbers, 1)

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

    lcmnum = (lcm(*Al))
    
    ans = 0
    for A in Al:
        ans += lcmnum//A
        ans %= (10**9+7)

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)

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

l = lcm(list(set(a)))
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

M = (10 ** 9 + 7)

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)
 
ans = 0
for a in A:
    ans = (ans + lcm_ // a) % M
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import array

n= int(input())

maxN = 1000000
a = list(map(int, input().split()))

def calculate_prime():
    primes = [True] * maxN
    primes[0] = primes[1] = False
    prim = []
    prime_map = dict()
    for i in range(2, maxN):
        if primes[i] == True:
            prime_map[i] = 0
            prim.append(i)
            j = i * i
            while j < maxN:
                primes[j]= False
                j+=i
    return prime_map, array.array('i',prim)

prime_map, prim = calculate_prime()

#print(prim)
for i in a:
    if i in prime_map:
        if prime_map[i] < 1:
            prime_map[i] = 1
    else:
        k = i
        for j in prim:
            if k % j == 0:
                tmp = 0
                while k % j == 0:
                    k = k // j
                    tmp += 1
                if tmp > prime_map[j]:
                    prime_map[j] = tmp
            if k in prime_map:
                if prime_map[k] < 1:
                    prime_map[k] = 1
                    break
            if k == 1:
                break

lcm = 1
for k, v in prime_map.items():
    if v > 0:
        lcm = lcm * (k**v)

#print(lcm)
result = 0

for i in a:
    result += lcm // i
    if result >= 1000000007:
        result = result % 1000000007

print(result)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N=int(input())
A=list(map(int,input().split()))
c=1
a=0
w=10**9+7
for A_ in A:
    c_=c*A_//fractions.gcd(c,A_)
    a=(a*c_//c+c_//A_)%w
    c=c_
print(int(a))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def power(x, y):
   if y == 0:
       return 1
   elif y == 1:
       return x % mod
   elif y % 2 == 0:
       return power(x, y/2) ** 2 % mod
   else:
       return power(x, (y-1)/2) ** 2 * x % mod

def main():
	N = INT()
	A = LIST()

	tmp = A[0]

	for i in range(1, N):
		tmp = (tmp*A[i])//gcd(tmp%A[i], A[i])
	# print(tmp)
	# B = [tmp//A[i] for i in range(N)]

	ans = 0
	for i in range(N):
		ans = (ans + tmp*power(A[i], mod-2)) % mod

	# for i in range(N):
	# 	ans = (ans+B[i])%mod
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

def add(a , b):
  mod = 1000000007
  return (a % mod + b%mod)%mod
n = int(input())
a = list(map(int,input().strip().split()))
ans = 1
sum = 0
for x in a:
  ans = (ans * x)//fun(ans , x)
for x in a :
  sum = add(sum , ans//x) 
print(sum)

Submission status: Time Limit Exceeded

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


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

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

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

print(ans)

Submission status: Time Limit Exceeded

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



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

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

ans = 0
MOD = 10**9+7

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
import copy

n=int(input().rstrip())
a=input().rstrip().split(" ")
stack=[]

for i in range(n):
    a[i]=int(a[i])
    #comon = (comon*a[i]//fractions.gcd(comon, a[i]))
b=copy.deepcopy(a)
while(len(b)>=2):
    for i in range(0,len(b),2):
        if(i ==len(b)-1):
            stack.append(b[i])
        else:
            stack.append((b[i]*b[i+1]//fractions.gcd(b[i], b[i+1])))
       # print(stack)
    b= copy.deepcopy(stack)
    stack=[]
comon=b[0]
ans=0
MOD=1000000000+7
for i in range(n):
    ans=ans+comon//a[i]
    ans=ans%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
p = mod - 2
X = []
while p != 0:
  X = [p%2] + X[:]
  p //= 2

def inved(x):
  y = 1
  for i in range(len(X)):
    if X[i] == 1:
      y *= x
      y %= mod
    if i != len(X) - 1:
      y *= y
      y %= mod
  return y

for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  L //= a
  b = A[i+1] // a
  L = a * b * L
S = 0
for i in range(N):
  S += (L * inved(A[i])) % mod
  S %= mod
print(S)

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

n=int(input())
a=[int(i) for i in 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])
    ans%=(10**9+7)
print(ans%(10**9+7))

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)

x = lcmm(A)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  if tmp%i == 0:
    continue
  tmp = i*tmp//fractions.gcd(i, tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
def ppp(): 
	N=int(input())
	a=list(map(int,input().split()))
	cnt=0

	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


	for i in a:
		cnt+=lcm(a)//i
		cnt=cnt%1000000007  
	return cnt
	
print(ppp())

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a,b):
    return (a*b)//gcd(a,b)
input()
a=[int(i) for i in input().split()]
l=a[0]
for i in a:
    l=lcm(i,l)
s=0
for i in a:
    s+=(l//i)
print(s%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = tuple(map(int,input().split()))
g = 1
MOD = 10**9+7
for i in range(N):
    g = g*a[i]//fractions.gcd(g,a[i])
res = 0
for i in range(N):
    res += (g//a[i])%MOD
print(res%MOD)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7

n=int(input())

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

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

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

lcma=1

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

ans=0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
MOD = 10**9 + 7

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

def GCP(a, b):
  if a < b:
    a, b = b, a
  while b > 0:
    a, b = b, a % b
  return a

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

T = deque(A)
while len(T) > 1:
  T.append(LCM(T.pop(), T.pop()))

L = T[0]

ans = 0
for i in range(N):
  ans += L // A[i]
  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))

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

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

count=0
for a in A:
    count+=(value//a)%mod
    count%=mod
print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

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

n = int(input())
aaa = get_nums_l()

g = lcm(aaa)

ans = 0
for a in aaa:
    ans = (ans + g//a) % (10**9+7)
print(ans % (10**9+7))

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(*numbers):
    return reduce(lcm_base, numbers, 1)

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

def LI():
  return [int(s) for s in input().split()]
 
N = int(input())
A_s = LI()
 
mod = 10**9 + 7
 
l = lcm_list(A_s)
 
print(sum(map(lambda x : l//x, A_s)) % mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]
for i in range(1,n):
  if lcm%A[i]!=0:
    lcm=lcm*A[i]//gcd(lcm,A[i])

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
a = int(input())
List=list(map(int,input().split()))
b = lcmm(List)
c = 0
for i in range(a):
  c = c + b // List[i] % 1000000007
print(c%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
if list_A[0] == list_A[-1]:
    print(N%(7+10**9))
else:
    for i in range(1, N):
        ans *= list_A[i] // fractions.gcd(ans, list_A[i])
    for a in list_A:
        sum += ans//a
    print(sum%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

#とりあえず。どうせTLE
sugoilcm = A[0]
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
for i in range(1,N):
    sugoilcm = A[i] * sugoilcm / gcd(A[i], sugoilcm)

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd


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()))
l = least_common_multiple(A)
ans = 0
MOD = 10**9+7
for a in A:
    ans = (ans + l // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def main():
    mod = 10**9 + 7

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n)) % mod
    print(t)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = 10**9 + 7

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


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


LCM = functools.reduce(lcm, A)
ans = sum([(LCM // a) % MOD for a in A]) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import functools
import numpy as np
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
def lcm_n(nums):
    return functools.reduce(lcm, nums)

n = ni()
a = na()
a_lcm = lcm_n(a)
a = np.array(a)
# ans = 0
# for ai in a:
#     ans += a_lcm // ai
#     ans %= mod
# print(ans)
ans = np.sum(a_lcm // a) % mod
print(ans)

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(*numbers):
    return reduce(lcm_base, numbers, 1)

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

denom = int(1e9+7)

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

lcm_A = lcm_list(A)

tot = 0
for elem in A:
    tot = (tot + lcm_A//elem)%denom
    
print(tot)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = i*tmp//fractions.gcd(i, tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
n = int(input())
a = list(map(int, input().split()))
def lcm_base(x, y):
    return (x*y) // fractions.gcd(x, y)

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

l = lcm(a)
mod = 10**9+7
total = 0
for i in a:
    total += l//i
    if total > mod:
        total %= mod
print(total)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import lru_cache

M = 10 ** 9 + 7

@lru_cache(maxsize=None)
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, x0, y0

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

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))


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

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
    
a = lcm(arr)
ans = []
for i in arr:
    ans.append((a//i)%1000000007)

print(sum(ans)%1000000007)

Submission status: Time Limit Exceeded

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

import fractions

mod = 10**9+7
num = 1
for i in range(N):
    num = num*A[i]//fractions.gcd(num, A[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
 
 
N=int(input())
a=list(map(int,input().split()))
cnt=0

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


for i in a:
	cnt+=lcm(a)//i
	cnt=cnt%1000000007  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from functools import reduce

def find_lcm(nums):
  # return reduce(lambda a,b: a*b // gcd(a,b), denominators)
  nums = list(set(nums))
  ans = nums[0]
  for n in nums[1:]:
    ans = ans * n // gcd(ans,n)
  return ans


def solve(nums):
  modula = 10**9 + 7
  lcm = find_lcm(nums)

  ans = 0
  for n in nums:
    ans += (lcm // n) % modula

  print(ans % modula)


def iin(): return int(input())
def iln(): return list(map(int, input().split()))


N = iin()
nums = iln()
solve(nums)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
li = sorted(list_A)
if li[0] == li[-1]:
    print(N%(7+10**9))
else:
    for i in range(1, N):
        ans *= list_A[i] // fractions.gcd(ans, list_A[i])
    for a in list_A:
        sum += ans//a
    print(sum%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
mod=10**9+7
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
lcm=A[0]
for i in range(1,n):
  lcm=lcm*A[i]//gcd(lcm,A[i])

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

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

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:
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
import fractions
a=l[0]
for i in range(1,n):
   l[i]%=mod
   a=(a*l[i]//(fractions.gcd(a,l[i])))
list=[(a//l[i]) for i in range(n)]
print(sum(list)%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    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 = zip(*c.most_common())

    L = values[0]
    for i in range(1, len(values)):
        L = L * values[i] // gcd(L, values[i])

    ans = 0
    for ci in range(len(values)):
        ans += (L // values[ci]) * counts[ci]
        ans %= INF
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

def lcm(a, b):
    x = a * b
    if(a<b):
        tmp = a
        a = b
        b = tmp

    r = a % b
    while(r!=0):
        a = b
        b = r
        r = a % b

    return x / b
    
MOD = 1000000007
n = int(input())
a = list(map(int, input().split())) 

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

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

print(int(ans))

Submission status: Time Limit Exceeded

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

MOD = 1000000007  # type: int


def solve(N: int, A: "List[int]"):
    lcm = 1
    AA = [0] * (1000001)
    for a in A:
        AA[a] += 1
    for i in range(1000001):
        if AA[i] != 0:
            lcm =  (lcm * i) // gcd(lcm, i)
    ans = 0

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

    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

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= k**(v - fs[k])
        a %= MOD
    ans += a
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
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 = list(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
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)

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
mod = 1000000007
for i in a:
    ans = (ans+(l//i))%mod
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
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])
total = 0
for i in range(0, n):
    b = ans // a[i]
    total += b % (10**9 + 7)
print(total % (10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

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

n = int(input())
aaa = get_nums_l()

g = lcm(aaa)

ans = 0
for a in aaa:
    ans += g//a
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

lcm = 1
for i in range(n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7

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

def GCP(a, b):
  if a < b:
    a, b = b, a
  while b > 0:
    a, b = b, a % b
  return a

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

T = A.copy()
while len(T) > 1:
  T.append(LCM(T.pop(0), T.pop(0)))

L = T[0]

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import lru_cache

M = 10 ** 9 + 7

@lru_cache(maxsize=None)
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, x0, y0

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

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

lcm_ = A[0]
for a in A[1:]:
    lcm_ = lcm_ * a // gcd(lcm_, a)

ans = 0
for a in A:
    m = modinv(a, 10 ** 9 + 7)
    ans = (ans + lcm_ * m) % M

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 10**9 + 7
n = int(input())
lst = list(map(int, input().split()))
koubai = lst[0]
for i in range(1, n):
    koubai = koubai*lst[i]//fractions.gcd(koubai, lst[i])

total = 0
for l in lst:
    b = koubai//l
    total += b
    total %= mod
print(total)

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)

x = lcmm(A)

B = []
for a in A:
    B.append(x//a)

print(sum(B) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7


def lcm(a, b):
    """
    aとbの最小公倍数を計算します。
    """
    return a // gcd(a, b) * b


def main():
    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)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
for j in range(len(a)):
    s=s+x/int(a[j])
print(int(s)%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
#a,b = map(int,input().split())
A2 = list(map(int,input().split()))
A = list(set(A2))
#A = [int(input()) for i in range(N)]
#A = [list(map(int,input().split())) for i in range(N)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def lcm(a,b):
    gcda = gcd(a,b)
    return a*b//gcda
def lcmlist(lista):
    if len(lista) == 1:
        return lista[0]
    else:
        from functools import reduce
        return reduce(lcm,lista)
mod = 10**9 + 7
lcml = lcmlist(A)
ans = 0
for i in A2:
    ans = (ans + lcml//i)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5)
from fractions import gcd
from functools import reduce

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

def main():
    N = int(input())
    A = sorted([int(i) for i in input().split()])
    MOD = 10**9+7

    GCD = gcd_list(A)
    LCM = lcm_list(A)
    ans = 0
    if GCD != 1 and LCM == A[-1]:
        for i in range(N):
            ans = (ans + A[-1] // A[i]) % MOD
    else:
        for i in range(N):
            ans = (ans + LCM // A[i]) % MOD

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = int(1e9) + 7

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

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

v = functools.reduce(lcm, A)
ans = 0
for a in A:
    ans = (ans + v // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
ov = 10**9+7
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
l = lcm(a)
def d(n):
  return l//n%ov
b= list(map(d,a))
print(sum(b)%ov)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt,ceil
from collections import defaultdict

lim = 10**4 + 10

def sieve(N):
    """Dumb sieve of Eratosthemes, O(N*log(log(N)))"""
    b = [True]*(N+1)
    b[0] = False
    b[1] = False

    lim = ceil(sqrt(N))
    i = 2
    while i <= lim:
        if b[i]:
            for n in range(i**2,N+1,i):
                b[n] = False
        i+=1
    
    return [i for i,b in enumerate(b) if b]

P = sieve(lim)

def factor(n):
    """Given prime list, factorize n. Format as dict of factors with counts."""
    if n in P: return {n: 1}

    F = []
    for p in P:
        while n%p == 0:
            n//=p
            F.append(p)
        if n in P:
            F.append(n)
            break
    else:
        if n != 1:
            F.append(n)

    C = {}
    for f in F:
        if f not in C:
            C[f] = 0
        C[f] += 1

    return C

mod = 1000000007

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

D = defaultdict(int)
for a in A:
    for f,cnt in factor(a).items():
        D[f] = max(D[f], cnt)
l = 1
for f,cnt in D.items():
    l = l*pow(f, cnt, mod) % mod

res = sum(l*pow(a, mod-2, mod) for a in A)
print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
#import numpy as np

mod=int(10**9+7)

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

#main
N=int(input())
A=list(map(int,input().split()))
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:
from fractions import gcd
# from functools import reduce

def find_lcm(nums):
  # return reduce(lambda a,b: a*b // gcd(a,b), denominators)
  ans = nums[0]
  for n in nums[1:]:
    ans = ans * n // gcd(ans,n)
  return ans


def solve(nums):
  modula = 10**9 + 7
  lcm = find_lcm(nums)

  ans = 0
  for n in nums:
    ans += (lcm // n) % modula

  print(ans % modula)


def iin(): return int(input())
def iln(): return list(map(int, input().split()))


N = iin()
nums = iln()
solve(nums)