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: Wrong Answer

Solution code:
import math

M = 10 ** 9 + 7

def calc_primes(n):
	max = math.ceil(math.sqrt(n))
	table = [True] * (max + 1)
	i = 2
	while i <= max:
		if table[i]:
			j = i * 2
			while j <= max:
				table[j] = False
				j *= 2
		
		i += 1
	primes = []
	for i in range(2, max + 1):
		if table[i]:
			primes.append(i)
	return primes

factor_cache = {}

def calc_factors(n):
	org_n = n
	if n in factor_cache:
		print("c")
		return factor_cache[n]
	max = math.ceil(math.sqrt(n))
	i = 0
	p = 2
	prime_count = len(primes)
	while True:
		if n % p == 0:
			factors = calc_factors(n // p).copy()
			if p in factors:
				factors[p] += 1
			else:
				factors[p] = 1
			factor_cache[n] = factors
			return factors
		else:
			i += 1
			if i >= prime_count:
				break
			p = primes[i]
	if n != 1:
		factors = {n: 1}
		factor_cache[org_n] = factors
		return factors
	else:
		return {}

N = int(input())

primes = calc_primes(N)

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

total_factors = {}
factors_list = []

for A in A_list:
	factors = calc_factors(A)
#	print(factors)
	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: Wrong Answer

Solution code:
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    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
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**6+1)

d = dict()

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if p in d:
            if c > d[p]:d[p] = c
        elif c != 0:
            d[p] = c
print(1)

Submission status: Wrong Answer

Solution code:
import math

M = 10 ** 9 + 7

def calc_primes(n):
	max = math.ceil(math.sqrt(n))
	table = [True] * (max + 1)
	i = 2
	while i <= max:
		if table[i]:
			j = i * 2
			while j <= max:
				table[j] = False
				j *= 2
		
		i += 1
	primes = []
	for i in range(2, max + 1):
		if table[i]:
			primes.append(i)
	return primes

primes = calc_primes(10000)

factor_cache = {}

def calc_factors(n):
	org_n = n
	if n in factor_cache:
		print("c")
		return factor_cache[n]
	max = math.ceil(math.sqrt(n))
	i = 0
	p = 2
	prime_count = len(primes)
	while True:
		if n % p == 0:
			factors = calc_factors(n // p).copy()
			if p in factors:
				factors[p] += 1
			else:
				factors[p] = 1
			factor_cache[n] = factors
			return factors
		else:
			i += 1
			if i >= prime_count:
				break
			p = primes[i]
	if n != 1:
		factors = {n: 1}
		factor_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)
#	print(factors)
	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: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce
lcm=lambda x,y:x//gcd(x,y)*y
MOD=10**9+7

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

c=sum(pow(a,MOD-2,MOD) for a in A)//MOD
l=reduce(lcm,A)//MOD

print(c*l//MOD)

Submission status: Wrong Answer

Solution code:
from functools import reduce
from fractions import gcd
 
N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Wrong Answer

Solution code:
from fractions import gcd


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


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
print(_lcm)
for a in A:
    ans += _lcm // a
    ans %= 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd


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


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
print(_lcm)
for a in A:
    ans += _lcm // a
    ans %= 100000007
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce
def lcm(x,y):
    return (x * y) // gcd(x, y)
MOD = 10**9+7


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

l = reduce(lcm,a)%MOD
ans=0
for i in range(n):
    ans+=l//a[i]%MOD
    ans%=MOD

print(int(ans))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
if n == 1:
	print(1)
else:
	lcm = a[0] * a[1] // gcd(a[0], a[1])
	for x in a[2:]:
		lcm = lcm * x // gcd(lcm, x)

Submission status: Wrong Answer

Solution code:
import fractions
import sys

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

sum_b = 0
ans = a[0]
for i in range(1, n):
    if ans % i == 0:
        ans = ans * a[i] / fractions.gcd(ans, a[i])
for i in range(n):
    sum_b += ans / a[i]

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

Submission status: Wrong Answer

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

N = pow(10,9)+7
def gcd(a,b):
    if a==0:return b
    return gcd(b%a,a)

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

hcm = arr[0]
for i in range(1,n):
    hcm = lcm(hcm,arr[i])

res = 0
for num in arr:
    res += (hcm//num)
    

print(res)

Submission status: Wrong Answer

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

N = pow(10,9)+7
def gcd(a,b):
    if a>b:return gcd(b,a)
    while b!=0:
        nb = b%a
        a = b
        b = nb
    return a

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

hcm = arr[0]
for i in range(1,n):
    hcm = lcm(hcm,arr[i])

res = 0
for num in arr:
    res += (hcm//num)
    

print(res)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
from fractions import gcd
def lcm(x,y):
  return x * y // gcd(x,y)
def list_gcd(list):
    c=list[0]
    for i in list:
        c=gcd(c,i)
    return c
def list_lcm(list):
  c=1
  for i in list:
    c=lcm(c,i)
  return c
a = [i//list_gcd(a) for i in a]
a = [list_lcm(a) // i for i in a]
print(sum(a))

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

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

a1 = a[0]
mod_sum = 0
mod1 = 1
for i,name in enumerate(a[1:]):
    b1 = name
    ab1 = lcm(a1, b1)
    mod1 =  (mod1*(ab1//a1) + (ab1//b1))%mod
    a1 = copy.deepcopy(ab1%mod)

print(mod1)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7

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

a1 = a[0]
mod1 = 1
for i,name in enumerate(a[1:]):
    b1 = name
    ab1 = lcm(a1, b1)
    mod1 =  (mod1*(ab1//a1)%mod + (ab1//b1)%mod)
    a1 = copy.deepcopy(ab1)

print(mod1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime
prime = primelist(1001)

def factorization(n):
    arr = []
    temp = n
    for i in prime:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

fact = [0] * (1000001)
pri = []
for i in range(n):
    f = factorization(a[i])
    for fac, c in f:
        fact[fac] = max(fact[fac], c)

fact_list = []
for i in range(1000001):
    if fact[i] > 0:
        fact_list.append((i, fact[i]))



"""
ans = 0
for i in range(n):
    m = modinv(a[i])
    for fac, c in fact_list:
        m *= pow(fac, c, mod)
        m %= mod

    ans += m
    ans %= mod
"""
#print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

from fractions import gcd

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

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

MOD = 10 ** 9 + 7

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

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans += c // x

print(ans)

Submission status: Wrong Answer

Solution code:
# = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
# = list(input())
# = [tuple(map(int, input().split())) for _ in range(n)]

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

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

MOD = 10 ** 9 + 7

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

c = p[0]
for x in p[1:]:
    c = c * x // gcd(c, x)

ans = 0
for x in p:
    ans += c // x

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import fractions as f
 
MOD = 1000000007  # type: int
 
 
def solve(N: int, A: "List[int]"):
    #lcm=np.lcm.reduce(A)
    lcm=A[0]
    for i in range(1,N):
        lcm=lcm*A[i]//f.gcd(lcm,A[i])%MOD
 
    ans=0
    for i in range(N):
        ans+=lcm//A[i]
    print(ans%MOD)
    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: Wrong Answer

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

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0
print(lcm)
print(b)

for j in range(len(b)):
    ans +=b[j]

ans%=1000000007

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def sieve(num):
    ret = [-1] * (num+1)
    ret[2] = 2
    primes = [2, 3]
    i = 3
    while i * i <= num:
        for prime in primes:
            if i % prime == 0:
                ret[i] = prime
                break
        if ret[i] == -1:
            primes.append(i)
            ret[i] = i
        i += 1
    return primes

def main():
    n = int(sys.stdin.readline().strip())
    a = [int(s) for s in sys.stdin.readline().strip().split(' ')]
    # n = 3
    # a = [2, 3, 4]
    a_max = max(a)
    primes = sieve(a_max+1)

    lcm = defaultdict(int)

    lcms = []

    for ai in a:
        cur = ai
        lcm_ai = defaultdict(int)
        for prime in primes:
            while cur % prime == 0:
                lcm_ai[prime] += 1
                cur //= prime
        lcms.append(lcm_ai)
        for key in lcm_ai.keys():
            lcm[key] = max(lcm[key], lcm_ai[key])

    MOD = 10 ** 9 + 7

    ans = 0
    for i in range(n):
        cur = 1
        for key in lcm.keys():
            diff = lcm[key] - lcms[i][key]
            cur *= pow(key, diff, MOD)
            cur %= MOD
        ans += cur
        ans %= MOD
    print(ans)

main()

Submission status: Wrong Answer

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

#------------最小公倍数---------------------
gcd = a[0]
for i in range(1, N):
    gcd = gcd * a[i] // fractions.gcd(gcd, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(gcd //a[i])
ans=0

if N%2==0:
    for i in range(0,N):
	    ans = b[i]+b[i-1]
else:
    #b.append(0)
    for i in range(0,N-1):
	    ans = b[i]+b[i-1]
    ans+= b[-1]


print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
N=int(input())
a = list(map(int, input().split()))
gcd = a[0]
for i in range(1, N):
    gcd = gcd * a[i] // fractions.gcd(gcd, a[i])

b= []
for i in range(N):
    b.append(gcd //a[i])
ans=0

if N%2==0:
    for i in range(0,N,2):
	    ans = (b[i]+b[i-1])%1000000007
else:
    b.append(0)
    for i in range(0,N,2):
	    ans = (b[i]+b[i-1])%1000000007


print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

lcm = lambda a, b: a * b // gcd(a, b)
mod = 10 ** 9 + 7

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

L = 1
for a in A:
    L = lcm(L, a)
    
L %= mod

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 5
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 5):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 5, p):
                p_candidate_list[q] = 0
    primes_1000000 = [p for p in range(100000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    # assert solve(5, [12, 12, 12, 12, 12]) == 5
    # assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 6
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 6):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 6, p):
                p_candidate_list[q] = 0
    primes_1000000 = [p for p in range(1000000) if p_candidate_list[p]]
    
    print(primes_1000000)

    lcm = 1
    for p in primes_1000000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    assert solve(5, [12, 12, 12, 12, 12]) == 5
    assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 3
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 3):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 3, p):
                p_candidate_list[q] = 0
    primes_1000 = [p for p in range(1000) if p_candidate_list[p]]
 
    lcm = 1
    for p in primes_1000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    assert solve(5, [12, 12, 12, 12, 12]) == 5
    assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007
 
 
def GCD(a, b):
    if b == 0:
        return a
    else:
        return GCD(b, a % b)
 
 
def modinv(a, mod=MOD):
    b = mod
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u
 
 
def LCM(a, b):
    return (a // GCD(a, b)) * b
 
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for i in range(n):
    l = LCM(l, a[i])
ans = 0
l %= MOD
for i in range(n):
    ans += l /a[i]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(x,y):
  return (y if x%y==0 else gcd(y,x%y))
def lcd(x,y):
  return x*y//gcd(x,y)
P=1000000007
N=int(input())
A=list(map(int,input().split()))
l=1
for a in A:
  l=lcd(a,l)
ans=0
for a in A:
  ans+=l*(a**(P-2))
print(ans%ans)

Submission status: Wrong Answer

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

def lcm(x, y):
    return x // gcd(x, y) * y
n = int(input())
a = list(map(int, input().split(' ')))
l = 1
for ai in a:
    l = lcm(l, ai)
print(l)
mod = 1000000007
ans = 0
for ai in a:
    ans += l // ai
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

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

L = 1
for a in A:
    L *= a * pow(gcd(L, a), mod - 2, mod)

L %= mod

print(sum(L * pow(a, mod - 2, mod) % mod for a in A) % mod)

Submission status: Wrong Answer

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**3)
for i in range(2,10**3):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**3,i):
        is_prime[j]=False

LCM=defaultdict(int)
for i in range(N):
    n=A[i]
    for j,p in enumerate(primes):
        tmp=0
        while n%p==0:
            tmp+=1
            n//=p
        LCM[j]=max(LCM[j],tmp)
    if n!=1:
        LCM[n]=max(LCM[n],1)
l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

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

print(ans)

Submission status: Wrong Answer

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**3)
for i in range(2,10**3):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**3,i):
        is_prime[j]=False

LCM=defaultdict(int)
for i in range(N):
    n=A[i]
    for j,p in enumerate(primes):
        tmp=0
        while n%p==0:
            tmp+=1
            n//=p
        LCM[j]=max(LCM[j],tmp)
    if n!=1:
        LCM[n]=max(LCM[j],1)
l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

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

print(ans)

Submission status: Wrong Answer

Solution code:
from functools import reduce
import fractions

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().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

print(sum)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
n = int(input())
a = [int(x) for x in input().split()]
sum = 0
G=1
for elem in a:
    G=lcm(G,elem)
for elem in a:
  sum+=G//elem
print(sum)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

lcm = lambda a, b: a * b * pow(gcd(a, b), mod - 2, mod)
mod = 10 ** 9 + 7

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

L = reduce(lcm, A) % mod
print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import numpy as np


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


def main():
    n = int(input())
    a_matrix = np.array(input().split()).astype(int)

    l = a_matrix[0]
    for a in a_matrix[1:]:
        l = lcm(l, a)

    l_matrix = np.zeros_like(a_matrix)
    l_matrix += l
    ans_matrix = l_matrix // a_matrix
    
    mod = 10 ** 9 + 7
    ans = ans_matrix.sum() % mod

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8

from fractions import gcd
n = int(input())
a = list(map(int, input().split(' ')))

mod = 10 ** 9 + 7

#最小公倍数を取得
g = a[0]
for num in a[1:]:
    g = g * num // gcd(num, g)

ans = 0
#計算後なのでmodオッケー
l = g % mod
for num in a:
    ans += l // num
    ans %= mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
import numpy as np


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


def main():
    n = int(input())
    a_matrix = np.array(input().split()).astype(int)

    l = a_matrix[0]
    for a in a_matrix[1:]:
        l = lcm(l, a)

    l_matrix = np.zeros_like(a_matrix)
    l_matrix += l
    ans_matrix = l_matrix // a_matrix
    ans = ans_matrix.sum()

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#coding:utf-8

from fractions import gcd
n = int(input())
a = list(map(int, input().split(' ')))

mod = 10 ** 9 + 7

#最小公倍数を取得
g = a[0]
for num in a[1:]:
    g = g * num // gcd(num, g)

ans = 0
#計算後なのでmodオッケー
l = g % mod
for num in a:
    ans += l // num
    ans %= mod
print(ans)

Submission status: Wrong Answer

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
for i in range(1, N):
  ans = 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: Wrong Answer

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

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

n=max(A)+5

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]
#print(table)

lcm=[0]*len(table)
p=[1]*len(table)



for i in range(N):
    a=A[i]
    for j in range(len(table)):
        if a*a<table[j]:
            k=bisect.bisect_left(table,a)
            if lcm[k]==0:
                lcm[k]=1
                p[k]=a
            
            break
        if a%p[j]==0:
            a=a//p[j]
            while a%table[j]==0:
                a=a//table[j]
                lcm[j]+=1
                p[j]*=table[j]
                
        
l=1
for j in range(len(table)):
    l*=p[j]
    

ans=0
mod=10**9+7

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

w=0
for i in A:
  w+=(ans//i)%(10**9+7)
  
print(w)

Submission status: Wrong Answer

Solution code:
import fractions

MOD = (10**9)+7
inv = [1]*(10**6+10)
for i in range(2,len(inv)):
    inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD

def lcm(a,b):
    return a*b*inv[fractions.gcd(a,b)]

n = int(input())
a = list(map(int,input().split()))
l = 1
for i in range(n):
    l = lcm(l,a[i])  #mod
l %= MOD

ans = 0
for i in range(n):
    ans = (ans+(l*inv[a[i]])%MOD)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
from fractions import gcd
mod = 10**9+7
g = A[0]
for a in A[1::]:
  g = g*a//gcd(g,a)

ans = 0
b = g%mod
for a in A:
  ans += b//a
  ans %= mod
  
print(ans%mod)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
lcm = lambda a, b: a * b // gcd(a, b)

mod = 10 ** 9 + 7


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

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

print(L)

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
 
input = sys.stdin.readline
 
import sys
import numpy as np
import fractions
 
N = int(input())

def LI():
  return [int(s) for s in input().split()]

A_s = np.array(LI(),dtype = 'int')
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

print(sum(l//A_s) % mod)

Submission status: Wrong Answer

Solution code:
import sys
 
input = sys.stdin.readline
 
import sys
import numpy as np
import fractions

 
input = sys.stdin.readline
ri = lambda: int(input())
ril = lambda: list(map(int, input().split()))
 
N = int(input())
A_s = np.array(ril(),dtype = 'int')
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

print(sum(l//A_s) % mod)

Submission status: Wrong Answer

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

# 参考：https://qiita.com/aki-takano/items/a43fac70b702d4f22d7e
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)
B = []
for a in A:
    B.append(a // L)

print(sum(B) % 1000000007)

Submission status: Wrong Answer

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

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


lcm=[0]*(10**6+5)



for i in range(N):
    a=A[i]
    b=int(math.sqrt(a))+1
    for j in range(2,b):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
    if a!=1:
        lcm[a]+=1
                
        
l=1
for j in range(2,len(lcm)):
    l*=pow(j,lcm[j])
    

ans=0
mod=10**9+7

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

Submission status: Wrong Answer

Solution code:
M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(x,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)