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 
def lcm_base(x, y):
  return(x * y) // gcd(x, y)
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

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

mod = 10**9 + 7
min = lcm_list(a)
sum = 0
for i in range(n):
  sum = sum + (min//a[i])%mod 
  
print(sum%mod)

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]

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline


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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


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

def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


def modinv(a, mod):
    return modpow(a, mod - 2, mod)


def cnk(a, b):
    MOD = 10**9+7
    ret = 1
    for i in range(b):
        ret *= (a-i)
        ret %= MOD
        ret = ret * modinv(i+1, MOD) % MOD
    return ret




def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    v = a[0]
    for i in range(1, n):
        v = lcm(v, a[i])
    
    ans = 0
    v %= MOD
    for i in range(n):
        ans += v * modinv(a[i], MOD) % MOD
        ans %= MOD
    print(int(ans))


            


    




    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	B=set(A)
	A=list(A)
	A.sort(reverse=True)
	a=1
	ans=0
	for i in A:
		g=gcd(a, i)
		ans *=i//g
		a=a*i//gcd(a, i)
		ans+=a//i
		ans%=mod
	
	
	
	
	print(ans)
	
	
	
	
	
	


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

P = 10**9 + 7
n = int(input())

def lcm(p,q):
    return p*q//gcd(p,q)

a = list(map(int, input().split()))
x = 1
for i in range(n):
    x = lcm(x,a[i])
ans = 0
for i in range(n):
    ans += x//a[i]
    ans = ans%P
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = [0 for _ in range(N)]
g = 0
for i,a in enumerate(map(int,input().split(" "))):
    A[i] = a
    if i == 0:
        g = a
    g = g*a//gcd(a,g)
ans = 0
A = tuple(A)
for a in A:
    ans += g//a
    ans %= (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappop, heappush
from random import randint
from collections import defaultdict
from itertools import accumulate
from fractions import gcd
import sys
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
MOD = 10**9 + 7
N = int(input())
A = inpl()
#N = 10**4
#A = [randint(0, 10**6) for _ in range(10**4)]

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

Submission status: Time Limit Exceeded

Solution code:
import math

M = 10 ** 9 + 7

cache = {}

def calc_factors(n):
	org_n = n
	if n in cache:
		return cache[n]
	max = math.ceil(math.sqrt(n))
	x = 2
	while x <= max:
		if n % x == 0:
			factors = calc_factors(n // x).copy()
			if x in factors:
				factors[x] += 1
			else:
				factors[x] = 1
			cache[n] = factors
			return factors
		else:
			x += 1
	if n != 1:
		factors = {n: 1}
		cache[org_n] = factors
		return factors
	else:
		return {}

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

total_factors = {}
factors_list = []

for A in A_list:
	factors = calc_factors(A)
	factors_list.append(factors)
	for factor, count in factors.items():
		if factor not in total_factors:
			total_factors[factor] = count
		elif total_factors[factor] < count:
			total_factors[factor] = count

total = 0
for A, factors in zip(A_list, factors_list):
	B = 1
	for factor, count in total_factors.items():
		if factor in factors:
			count -= factors[factor]
#		for _ in range(count):
#			B = (B * factor) % M
		B = (B * pow(factor, count, M)) % M
	total = (total + B) % M

print(total)

Submission status: Time Limit Exceeded

Solution code:
import fractions
  
N = int(input())
A = tuple(map(int, input().split()))

ans = 0
MOD = 10**9 + 7

LCM = A[0]
for i in range(1, N):
    LCM *= A[i]//fractions.gcd(LCM, A[i])
    
for a in A:
  ans += LCM//a
  ans = ans%MOD
  
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
MOD = 10**9 + 7

LCM = A[0]
for i in range(1, N):
    LCM *= A[i]//fractions.gcd(LCM, A[i])
    
for a in A:
  ans += LCM//a
  ans = ans%MOD
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
import fractions



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

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

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

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

MOD = 10 ** 9 + 7
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, 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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

ans = 0
for i in a:
    ans += b // i
    ans %= 10**9+7

print(ans)

Submission status: Time Limit Exceeded

Solution code:


import numpy as np

import math

def acinput():
    return list(map(int, input().split(" ")))


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


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


def lcm_list(numbers):
    res=numbers[0]
    for n in numbers:
        res=lcm_base(n,res)
    return res

N=int(input())
a=np.array(acinput())
s=np.array(lcm_list(a))
v=s/a
print(int(np.sum(v))%(10**9+7))

#print(v)
#print(s)

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)

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

mod = 1000000000 + 7
min = lcm_list(a)
sum = 0
for i in range(n):
  sum = sum + (min//a[i])%mod 
  
print(sum%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
import fractions



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

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

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

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()

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
#-------------------------------------------------------------------
def gcd_impl(n, m):
	for i in range(10):
		t = n - m
		
		if (m > t):
			n,m = m, t
		else:
			n,m = t, m
		
		if( m == 0 ): return n

	return gcd_impl( m, n % m )


def gcd(n, m):
	if n < m: n,m=m,n
	return gcd_impl( n, m )

#-------------------------------------------------------------------
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:
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
N=input()
A=list(map(int,input().split(' ')))
ans = 0
l = 1
mod = 10**9+7
for i in A:
    g = gcd(l,i)
    l = l*i//g
print(sum([l//i%mod for i in A])%mod)

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 a:
    res += g//i
print(res%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

p = 10**9+7
ans = 0

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

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

lcm = lcm_list(A)

for i in A:
    ans += lcm // i % p

print(ans%p)

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 1000000007

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

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

lcm = 1
for i in A: lcm = LCM(lcm, i)

ans = 0
for i in A:
    ans += lcm // i
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# 逆元なしでいけるか確認

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


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

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

print(ans)

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 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 = I()
a = LI()
l = lcm(a)
ans = 0
for i in a:
    ans += l*pow(i,mod-2,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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


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


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


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

MOD = 10 ** 9 + 7
ans = 0
for a in A:
    ans += l * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import random
from fractions import gcd
lim=10**9+7
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)
n=int(input())
#A=random.sample(list(range(1, 10**6)), k=10**4)
A=[int(i) for i in input().split()]
Z=lcm(A)
ans=0
for a in A:
    ans += Z//a
print(ans % lim)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = [int(i) for i in input().split()]

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

ans = 0
for i in a:
    ans += b // i

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

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

count=0
for i in range(n):
  count+=(ans//a[i])
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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:
#互いに素なa,bについて、a*x+b*y=1の一つの解
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

def mod_inv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

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

ans = 0
for i in range(n):
    k = mod_inv(a[i], mod)
    ans += lcm * k
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
for e in A:
    t = lcm(e,t)

ans = 0
for e in A:
    ans += t//e
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

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)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# 工夫せずにやって通るか確認

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


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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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())
a = list(map(int, input().split()))

div = 10**9 + 7
lcm_num = lcm(a)
ans = [(lcm_num // ai) % div for ai in a]

print(sum(ans)%div)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
import fractions



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

    x = 1
    for a in A:
        x = (a * x) // fractions.gcd(a, x)

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

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

N, *A = map(int, open(0).read().split())

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

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

MOD = 10 ** 9 + 7
num = lcm_list(A)
print(sum(num // v for v in A) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions

MOD = 1000000007
inv = [1] * 1001001

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

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

for i in range(2, 1001001):
    inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD

lcm = 1
for i in A:
    lcm = LCM(lcm, 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

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

p = 10**9+7

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

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

lcm = lcm(*A)

B = [lcm//i for i in A]

print(sum(B)%p)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

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

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

print(ans%MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2000000)

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


mod = 1000000007


def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))



n=int(input())
aa=[]
aa=list(map(int,input().split()))
# for i in range(n):
#     aa.append(randint(1,10**6))

bb=lcm(aa)
mod=10**9+7
ans=0
for i in range(n):
    ccc=div(bb,aa[i])
    ans=int((ccc%mod+ans%mod)%mod)
print(int(ans))

Submission status: Time Limit Exceeded

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

from fractions import gcd

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

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

b = [0] * n
b[0], b[1] = a[1] // gcd(a[0], a[1]), a[0] // gcd(a[0], a[1])

for i in range(2, n): # nの小さい値について例外処理
    l = lcm(a[i-1] * b[i-1], a[i])
    b[i] = l // a[i]
    u = (a[i] * b[i]) // (a[i-1] * b[i-1])
    for j in range(i):
        b[j] *= u

ans = sum(b)
print(ans % 1000000007)

# PyPy案件

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)

n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0

for i in range(n):
    ans += x // l[i]
    ans %= (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

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


def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    A = np.array(a)

    lcm = reduce(lcm_base, a, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

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

L = A[0]
for a in A:
  L = lcm(a,L)
ans = 0
for a in A:
  #ans += L//a
  ans += L*pow(a,MOD-2,MOD)
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce


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


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans = (ans + L * pow(i, mod - 2, mod)) % mod

print(ans % mod)

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 lcma(numbers):
    return reduce(lcm_base, numbers, 1)
 
a = lcma(arr)
ans = [(a//i)%1000000007 for i in arr]
cnt=0
for i in ans:cnt = cnt+ i %1000000007
print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import fractions
a = list(map(int, input().split()))
lcm = a[0]
for i in a:
  lcm = lcm * i // fractions.gcd(lcm, i)
b=[]
for i in a:
  b.append(lcm//i)
ans=sum(b)%(10**9+7)
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 lcm_list(numbers):
  return reduce(lcm, numbers, 1)

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

l = lcm_list(A)
ans = sum([l // x for x in A]) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
l=list(map(int,input().split()))
mod=10**9+7
import fractions
lmc=l[0]
for i in range(1,n):
   l[i]%=mod
   lmc=(lmc*l[i]//(fractions.gcd(lmc,l[i])))
ans=0
for i in range(n):
    ans += lmc*pow(l[i],mod-2,mod)
    ans %= mod
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
b = [lcm//L[i] for i in range(N)]
print(sum(b)%(u))

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])%1000000007
print(result%1000000007)

Submission status: Time Limit Exceeded

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


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

MOD = 10 ** 9 + 7
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions
import sys
sys.setrecursionlimit(20000)

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


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

N = int(input())
A = sorted(list(map(int, input().split())))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in A:
    ans += ll // i
print(int(ans%mod))

Submission status: Time Limit Exceeded

Solution code:
import fractions
#import math
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)

n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
b = lcm(*a)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

MOD = 1000000000 + 7

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

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

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += (l // i) % MOD
print(int(ans % MOD))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = tuple(map(int,input().split(" ")))
g = A[0]
l = 1
for i in range(N):
    g = g*A[i]//gcd(A[i],g)
ans = 0
for i in range(N):
    ans += g//A[i]
    ans %= (10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
MOD = 10**9+7
def gcd(a, b):
    while a and b:
        if a > b:
            a %= b
        else:
            b %= a
    return max(a, b)

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

_a = a_ls[0]
for a in a_ls:
    _a = lcm(_a, a)
ls = [_a // a % MOD for a in a_ls]
print(sum(ls) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
lcm = A[0]
MOD = 10**9 + 7
for a in A:
    lcm = (lcm // gcd(lcm,a) * a)
res = 0
for a in A:
    res = (res + lcm // a) % MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

p = 10**9+7

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

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

lcm = lcm_list(A)

B = [lcm//i for i in A]

print(sum(B)%p)

Submission status: Time Limit Exceeded

Solution code:
import fractions 
N=int(input())
A=list(map(int,input().split()))
t=1
for i in A:
  t=(t*i)//fractions.gcd(t,i)
ans=0
for i in A:
  ans+=t//i
  ans%=(10**9+7)
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)