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 fractions
import collections
import copy

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

num = 10**3

mod = 10**9+7

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

com_ab = [0]*(num)

for i in range(n):
    #print(len(b_li[i]))
    keys = pri_li[i].keys()
    #print(keys)
    for j in keys:
        if j > num:
            exit()
        com_ab[j] = max(com_ab[j],pri_li[i][j])

"""
for i in range(10**3):
    if com_ab[i] > 0:
        com_num *= pow(i,com_ab[i],mod)
"""
ans = 0

for i in range(n):
    com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    keys = pri_li[i].keys()
    for j in keys:
        com_ab_new[j] -= pri_li[i][j]
    kari = 1
    for j in range(num):
        if com_ab_new[j] > 0:
            kari *= pow(j,com_ab_new[j],mod)
    ans += kari
    ans %= mod
    #print(ans)
        
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
import collections
import copy

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

mod = 10**9+7

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))

pri_li0 = copy.copy(pri_li[0])

for i in range(n-1):
    pri_li[0] += pri_li[i+1]

b_li = [pri_li[0]-pri_li0]

for i in range(1,n):
    b_li.append(pri_li[0]-pri_li[i])

com = copy.copy(b_li[0])
#print(com)
for i in range(1,n):
    com &= b_li[i]
#print(com)
#exit()
for i in range(n):
    b_li[i] -= com

ans = 0
exit()
for i in range(n):
    tmp = 1
    #print(len(b_li[i]))
    keys = b_li[i].keys()
    #print(keys)
    for j in keys:
        #print(b_li[i][j])
        #exit()
        tmp *= pow(j, b_li[i][j],mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import fractions
import collections
import copy

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

mod = 10**9+7

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

pri_li = []

for i in range(n):
    pri_li.append(collections.Counter(prime_factorize(ai[i])))
exit()
pri_li0 = copy.copy(pri_li[0])

for i in range(n-1):
    pri_li[0] += pri_li[i+1]

b_li = [pri_li[0]-pri_li0]

for i in range(1,n):
    b_li.append(pri_li[0]-pri_li[i])

com = copy.copy(b_li[0])
#print(com)
for i in range(1,n):
    com &= b_li[i]
#print(com)
#exit()
for i in range(n):
    b_li[i] -= com

ans = 0

for i in range(n):
    tmp = 1
    #print(len(b_li[i]))
    keys = b_li[i].keys()
    #print(keys)
    for j in keys:
        #print(b_li[i][j])
        #exit()
        tmp *= pow(j, b_li[i][j],mod)
        tmp %= mod
    ans += tmp
    ans %= mod

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

mod = 10 ** 9 + 7
def modpow(a, x):
    if a == 0:
        return 0
    if x == 0:
        return 1
    elif x % 2 == 0:
        return modpow((a * a) % mod, x // 2) % mod
    else:
        return (modpow((a * a) % mod , x // 2) % mod * a) % mod


def factorization(x):
    ans = []
    i = 2
    in_x = x
    while i <= x:
        count = 0
        while x % i == 0:
            x = x // i
            count += 1
        if count > 0:
            ans.append((i, count))
        i += 1
    return ans


N = int(input())
A = list(map(int, input().split(" ")))
primes = {}
for a in A:
    factors = factorization(a)
    for f in factors:
        if f[0] in primes:
            primes[f[0]] = max(primes[f[0]], f[1])
        else:
            primes[f[0]] = f[1]

lcm = 1
print(primes)
for p in primes:
    lcm *= modpow(p, primes[p])
    lcm %= mod


ans = 0
for a in A:
    ans += (lcm * modpow(a, mod - 2)) % mod
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
def solve(num):
    result = []
    for i in range(2, int(num**(1/2)+1)):
        c = 0
        if num%i==0:
            while num%i==0:
                c += 1
                num //= i
            result.append([i, c])
    if len(result)==0:
        result=[[num, 1]]
    return result

n = int(input())
a = list(map(int, input().split()))
a_memo = []
memo = {}
for i in a:
    i_memo = solve(i)
    a_memo.append(i_memo)
    for s, t in i_memo:
        if s in memo:
            memo[s] = max(memo[s], t)
        else:
            memo[s] = t

result, mod = 0, 10**9+7
for i in range(n):
    x = copy.deepcopy(memo)
    for s, t in a_memo[i]:
        x[s] -= t
    z = 1
    for s, t in x.items():
        z *= pow(s, t)
    result = (result+z)%mod
print(result)

Submission status: Wrong Answer

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

l = 1
for a in A:
    l = a*l//(gcd(a,l))
ans = 0
for a in A:
    ans += l//a
    if ans >= MOD:
        ans -= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(input())
    a = list(map(int, readline().split()))

    def enum_primes(n):
        flag_num = (n + 1) // 2
        prime_flag = [True] * flag_num
        primes = [2]

        if n == 2:
            return primes

        for i in range(1, int(n ** 0.5) + 1, 2):
            if prime_flag[i]:
                p = 2 * i + 1
                for j in range(2 * i * (i + 1), flag_num, p):
                    prime_flag[j] = False

        temp = [i * 2 + 1 for i in range(1, flag_num) if prime_flag[i]]
        primes.extend(temp)

        return primes

    amax = max(a)
    if amax == 1:
        print(n)
        sys.exit()

    lim = int(amax ** 0.5 + 5)
    primes = enum_primes(lim)

    def factorization(n):
        factors = []

        if n in primes:
            return Counter([n])

        for i in primes:
            while n % i == 0:
                factors.append(i)
                n //= i

        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

    for i, num in enumerate(a):
        a_fac[i] = factorization(num)

    lcm = {1: 1}

    for fac in a_fac:
        for key, value in fac.items():
            lcm[key] = max(lcm.get(key, 0), value)

    ans = 0

    for fac in a_fac:
        temp = 1
        for key, value in lcm.items():
            p = value - fac.get(key, 0)
            temp *= pow(key, p)
            temp %= MOD
        ans += temp
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

inverse = [1] * (max_a + 1)
for i in range(2, max_a + 1):
  inverse[i] = -inverse[i % mod] * (mod // i) % mod

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

sum_b = 0
for i in range(n):
  sum_b = (sum_b + lcm * inverse[a[i]]) % mod
print(sum_b)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

divisor = a[0]
prod_a = a[0]
for i in range(1, n):
  divisor = gcd(divisor, a[i])
  prod_a = (prod_a * a[i]) % mod

sum_b = 0
inv_divisor = pow(divisor, mod - 2, mod)
for i in range(n):
  sum_b = (sum_b + prod_a * inv_divisor) % mod
print(sum_b)

Submission status: Wrong Answer

Solution code:
import fractions
mod = 10 ** 9 + 7

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

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

LCM = 1
for i in a:
    LCM = lcm(LCM,i)
    LCM %= mod

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

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

LCM = 1
for num in nums:
    LCM = lcm(num, LCM)
LCM %= mod
ans = 0
for num in nums:
    ans += (LCM // num) % mod
print(ans % mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
l = lc%mod
for i in range(1, n):
    lc = l * num[i] // fractions.gcd(lc, num[i])
    l = lc%mod
lc %= mod    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
l = lc%mod
for i in range(1, n):
    lc = l * num[i] // fractions.gcd(lc, num[i])
    l = lc%mod
    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
for i in range(1, n):
    lc = lc * num[i] // fractions.gcd(lc, num[i])
    lc %= mod
    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

ans =0
for i in range(n):
  ans += lc*modinv(num[i],mod)
  ans %= mod
print(ans)

Submission status: Wrong Answer

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


n = int(input())
a = list(map(int, input().split(" ")))
alcm = a[0]
for i in a:
    alcm = lcm(alcm, i)

tot = 0
for num in a:
    tot += alcm // num

print(tot % 1000000007)

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_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

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

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 Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

n = onem()

a = l()

po = max(a)

pr = make_primes(po)
g = cl.defaultdict(int)

ak = [cl.defaultdict(int) for i in range(n)]

for i in range(n):
    ppp = a[i]
    un = prime_decomposition(ppp)
    un = s(un)
    for j in un:
        g[j[0]] = max(g[j[0]],j[1])
        ak[i][j[0]] = j[1]

ans = 0
"""
for i in range(n):
    ui = 1
    for j in pr:
        ui *= pow_k(j,(g[j] - ak[i][j]))
    ans += ui
    ans %= mod
print(ans)

"""

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

mod=10**9+7

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

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

mod=10**9+7

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

L=A[0]
for i in range(1,n):
    L=lcm(L,A[i])
L%=mod

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

mod=10**9+7

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

L=A[0]
for i in range(n):
    L=lcm(L,A[i])

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

Submission status: Wrong Answer

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

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


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


def solve(N: int, A: "List[int]"):
    m = lcm(*A)
    sum = 0
    for a in A:
        sum = (sum + m*pow(a, MOD-2, MOD)) % MOD
    print(sum)
    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:
#!/usr/bin/env python3
import sys
from functools import reduce
import fractions
import math
from collections import defaultdict

MOD = 1000000007  # type: int


def prime_list(N):
    r = math.ceil(math.sqrt(N))
    table = [True]*(N-1)
    result = []
    for i in range(2, r+1):
        if table[i-2]:
            for j in range(2, N+1):
                if j % i == 0:
                    table[j-2] = False
            result.append(i)
    for i in range(r+1, N+1):
        if table[i-2]:
            result.append(i)
    return result


def prime_factorization(primes, N):
    pi = 0
    dict = defaultdict(int)
    prime = True
    while pi < len(primes):
        if N < primes[pi]:
            break
        if N % primes[pi] != 0:
            pi += 1
            continue
        N //= primes[pi]
        dict[primes[pi]] += 1
        prime = False
    if prime:
        dict[N] = 1
    return dict


def solve(N: int, A: "List[int]"):
    primes = prime_list(10**3)
    factorized = [prime_factorization(primes, A[i]) for i in range(N)]
    lcm = defaultdict(int)
    for f in factorized:
        for p in f:
            lcm[p] = max(lcm[p], f[p])
    sum = 0
    for f in factorized:
        a = 1
        for p in lcm:
            if lcm[p] > f[p]:
                a = a*p**(lcm[p]-f[p]) % MOD
        sum = (sum + a) % MOD
    print(sum)

    # m = lcm(*A)

    # def sumup(x, y):
    #     return (x + m // y) % MOD
    # print(reduce(sumup, A, 0))
    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 sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]


NN = 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
def prime_factrize(n):
    res = []
    while n != 1:
        prime = min_factor[n]
        exp = 0
        while min_factor[n] == prime:
            exp += 1
            n //= prime
        res.append([prime, exp])
    return res


n = INT()
a = LIST()
ll = []
for i in range(n):
    aa = prime_factrize(a[i])
    strt = 0
    for j in range(len(aa)):
        flag = True
        for k in range(strt, len(ll)):
            if aa[j][0] == ll[k][0]:
                ll[k][1] = max(ll[k][1], aa[j][1])
                strt = k
                flag = False
                break
        if flag:
            ll.append(aa[j])
l = 1
for i in range(len(ll)):
    l *= pow(ll[i][0], ll[i][1], mod)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)

Submission status: Wrong Answer

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


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


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

MOD = 1000000007
l = A[0]
for i in A[1:]:
    l = lcm(l, i)

ans = 0
for x in A:
    ans += l // x

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0:
        a, b = b, a % b
    return b 

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    gcdA = A[0]
    lcmA = A[0]
    for i in range(1, N):
        gcdA = gcd(lcmA, A[i])
        lcmA *=  (A[i] * pow(gcdA, mod - 2, mod)) % mod
        lcmA %= mod
    Ans = 0
    for a in A:
        Ans += (lcmA * pow(a, mod - 2, mod)) % mod
        Ans %= mod
    print(Ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import fractions
mod=10**9+7
def lcm(a,b):
    return a*b//fractions.gcd(a,b)


n=int(input())
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*pow(A[i],mod-2,mod))%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
"""素因数分解"""
def prime_decomposition(n):
    i = 2
    tank = []
    while i * i <= n:
        while n%i == 0:
            n /= i
            tank.append(i)
        i += 1
    if n > 1:
        tank.append(int(n))
    return dict(Counter(tank))

def main():
    n = int(input())
    A = list(map(int,input().split()))
    dct = {}
    for a in A:
        tmp = prime_decomposition(a)
        for k, v in tmp.items():
            if k not in dct.keys():
                dct[k] = v
            else:
                if v > dct[k]:
                    dct[k] = v
    l = 1
    for k,v in dct.items():
        l *= k**v
    res = 0
    for a in A:
        res += l//a
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = [int(x) for x in input().split()]
am = max(a)
mod = 10**9+7
if n==1:
    print(1)
    sys.exit()
li = [0]*(am+1)
lcm = 1
for k in range(n):
    z = a[k]
    for i in range(2,int(z**0.5)+1):
        x = 0
        while z%i==0:
            x += 1
            z//=i
        li[i] = max(li[i],x)
    if z!=1 :
        li[z] = 1

for i in range(2,am+1):
    if li[i]>0:
        lcm = lcm * i**li[i] % mod

ans = 0
for i in range(n):
    m = pow(a[i],mod-2,mod)
    ans = (ans+(lcm*m)%mod)%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = [int(x) for x in input().split()]
am = max(a)
mod = 10**9+7
if n==1:
    print(1)
    sys.exit()
li = [0]*(am+1)
lcm = 1
for k in range(n):
    z = a[k]
    for i in range(2,int(z**0.5)+1):
        x = 0
        while z%i==0:
            x += 1
            z//=i
        li[i] = max(li[i],x)
    if z!=1 :
        li[z] = 1

for i in range(2,am+1):
    if li[i]>0:
        lcm = lcm * i**li[i] % mod

ans = 0
for i in range(n):
    m = pow(a[i],mod-2,mod)
    ans = (ans+(lcm*m)%mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

n = int(input())
a = [int(x) for x in input().split()]
am = max(a)
mod = 10**9+7
if n==1:
    print(1)
    sys.exit()
li = [0]*(am+1)
lcm = 1
for k in range(n):
    z = a[k]
    for i in range(2,int(z**0.5)+1):
        x = 0
        while z%i==0:
            x += 1
            z//=i
        li[i] = max(li[i],x)
    if z!=1 :
        li[z] = 1

for i in range(2,am+1):
    if li[i]>0:
        lcm = (lcm*i*li[i])%mod

ans = 0
for i in range(n):
    m = pow(a[i],mod-2,mod)
    ans = (ans+(lcm*m)%mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

def main():
    n=int(input())
    a=list(map(int,input().split()))
    s=a[0]
    mod=10**9+7
    for i in a[1:]:
        s=(s*i*pow(gcd(s,i),mod-2,mod))%mod
    ans=0
    for i in range(n):
        ans+=pow(a[i],mod-2,mod)
    ans=(ans*s)%mod
    print(ans)
          
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd
mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
ans = 0
l = 1
for i in a:
    l = l*i//gcd(l,i)
    l %= mod
for i in a:
    ans = (ans +l*pow(i,mod-2,mod)) % mod
print(ans)

Submission status: Wrong Answer

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

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

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

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

law = 10 ** 9 + 7
ans = 0
for x in a:
    ans += l // x
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(np.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= i ** v
    l %= mod

r = powmod(a, mod-2, mod)
print(int(sum(l * r) % mod))

Submission status: Wrong Answer

Solution code:
from functools import lru_cache
import numpy as np


@lru_cache(maxsize=None)
def lcm(x, y):

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

    return x * y // gcd(x, y)


n = int(input())
a = np.array(list(map(int, input().split())))
mod = 10**9 + 7
x = a[0]

for i in a[1:]:
    x = lcm(x, i)
r = x / a
print(int(sum(r) % mod))

Submission status: Wrong Answer

Solution code:
import math
import fractions
import functools
def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    M = 10**9+7
    culcm = functools.reduce(lcm,a)

    result = functools.reduce(lambda p,q:(p+culcm//q)%M,a)

    print(result)

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**3)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかと、割り尽くした残りを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num, a

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。

ただし素数テーブルは1000までしか用意してないので、それ以上の素数はリストAの中に吐き出させ、
あとでそれをLに組み込む。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        cand, A[i] = div(A[i], p)
        e = max(e, cand)
    L *= pow(p, e, mod)
for a in A:
    L *= a
    L %= mod

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

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 1000)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        e = max(e, div(A[i], p))
    L *= pow(p, e, mod)

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

Submission status: Wrong Answer

Solution code:


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
def main():
  mod = 10**9 +7
  n = int(input())
  ls = list(map(int,input().split()))
  
  t = 1
  for a in ls:
    t = gcd(t,a)
  
  ans = 0
  for a in ls:
    ans = (ans + t//a) % mod 
  print(ans)
  
if __name__ == '__main__':
  main()

Submission status: Wrong Answer

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

p = [0]*10**6
for i in a:
    for j in range(2,ma+1):
        count = 0
        while i%j == 0:
            count += 1
            i /= j
        if count > p[j-1]:
            p[j-1] = count
        if i == 1:
            break
            
k=1
for i in range(10**6):
    if p[i] != 0:
        k *= (i+1)**p[i]

ans = 0
for i in a:
    ans += k/i
    
print(int(ans)%(10**9+7))

Submission status: Wrong Answer

Solution code:
def read_values():
    return map(int, input().split())
 
 
def read_list():
    return list(read_values())

def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
  
    u = {}
    for a in A:
      m = 2
      while m * m <= a:
        c = 0
        while a % m == 0:
          c += 1
          a //= m
        if c > 0:
          u[m] = max(u.get(m, 0), c)
        m += 1
      if a > 1:
        u[a] = max(u.get(a, 0), 1)

    lcm = 1
    for k, v in u.items():
      lcm *= pow(k, v, mod)
      lcm %= mod

    ans = 0
    for a in A:
      ans += lcm // a
      ans %= mod

    print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
def read_values():
    return map(int, input().split())
 
 
def read_list():
    return list(read_values())

def main():
    mod = 10 ** 9 + 7
    N = int(input())
    A = read_list()
  
    u = {}
    for a in A:
      m = 2
      while m * m <= a:
        c = 0
        while a % m == 0:
          c += 1
          a //= m
        if c > 0:
          u[m] = max(u.get(m, 0), c)
        m += 1
      if a > 1:
        u[a] = max(u.get(a, 0), 1)

    lcm = 1
    for k, v in u.items():
      lcm *= pow(k, v, mod)
      lcm %= mod

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

    print(ans)

if __name__ == "__main__":
  main()