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

def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

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

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)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

MOD=10**9+7
prime=Sieve_of_Eratosthenes(10**3+1)
dic={}
for p in prime:
    dic[p]=0

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

zz=set()
for i in range(n):
    x=a[i]
    tmpdic={}
    for p in prime:
        if x==1: break
        while x%p==0:
            x=x//p
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1

    if x>1:
        if x not in prime: zz.add(x)
        else:
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1

    
    for p in tmpdic:
        dic[p]=max(tmpdic[p],dic[p])

lcm=1
for p in dic:
    for j in range(dic[p]):
        lcm=(lcm*p)%MOD
for p in zz:
    lcm=(lcm*i)%MOD

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 21:14:43 2020

@author: masat
"""
import fractions

N = int(input())

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

A_list_2 = []
for i in A_list:
    gcd_i = fractions.gcd(A_list[0], i)
    A_list_2.append(i//gcd_i)

"""
    if i % A_list[0] == 0:
        A_list_2.append(i//A_list[0])
    else:
        A_list_2.append(i)
"""

GCD = 1
LCM = 1
for i in A_list_2:
    GCD = fractions.gcd(GCD,i)
    LCM = (LCM*i)//GCD

Bmax = LCM * A_list[0]

answer = 0

for i in A_list:
    answer += Bmax//i

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N = int(input())
A = list(map(int, input().split(' ')))
lcm = A[0]
for i in A[1:]:
    lcm = lcm*i // gcd(lcm, i)
ans = 0
for i in range(len(A)):
    ans += (lcm // A[i]) % 1000000007
print(int(ans))

Submission status: Wrong Answer

Solution code:
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 * pow(gcd(a, b), MOD - 2, MOD)


LCM = A[0]
for a in A:
    LCM = lcm(LCM, a)
LCM %= MOD

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

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import math

def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime

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

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)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

MOD=10**9+7
prime=Sieve_of_Eratosthenes(10**3+1)
dic={}
for p in prime:
    dic[p]=0

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

zz=[]
for i in range(n):
    x=a[i]
    y=int(x**(0.5))+1
    tmpdic={}
    for p in prime:
        if x==1: break
        while x%p==0:
            x=x//p
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1

    if x>1:
        if x not in prime: zz.append(x)
        else:
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1

    
    for p in tmpdic:
        dic[p]=max(tmpdic[p],dic[p])

lcm=1
for p in dic:
    for j in range(dic[p]):
        lcm=(lcm*p)%MOD
for i in zz:
    lcm=(lcm*i)%MOD

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

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    l = 1
    for a in A:
        l *= a//gcd(l,a)
    print(sum([l//a for a in A]))
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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


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

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

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

print(ans % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

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 * pow(gcd(a, b), MOD - 2, MOD)


X = deepcopy(A)
while len(X) > 1:
    a, b = X.pop(), X.pop()
    X.append(lcm(a, b))
LCM = X[0] % MOD

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

print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import math

def Sieve_of_Eratosthenes(N):
    if N<2: return set()
    prime=set(i for i in range(2,N+1))
    for i in range(2,math.ceil(N**0.5)+1):
        tmp=set()
        for j in prime:
            if j>i and j%i==0: tmp.add(j)
        for j in tmp:
            prime.remove(j)

    return prime



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

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)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m

MOD=10**9+7
prime=Sieve_of_Eratosthenes(10**3+1)
dic={}
for p in prime:
    dic[p]=0

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

zz=[]
for i in range(n):
    x=a[i]
    y=int(x**(0.5))+1
    tmpdic={}
    for p in prime:
        if p>y or x==1: break
        while x%p==0:
            x=x//p
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1

    if x>1:
        if x not in dic: zz.append(x)
        elif x in tmpdic: tmpdic[x]+=1
        else: tmpdic[x]=1

    
    for p in tmpdic:
        dic[p]=max(tmpdic[p],dic[p])

lcm=1
for p in dic:
    for j in range(dic[p]):
        lcm=(lcm*p)%MOD
for i in zz:
    lcm=(lcm*i)%MOD

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

Submission status: Wrong Answer

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)
lcm %= MOD
ans = 0
for i in A:
    ans += lcm//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 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*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

d = defaultdict(int)


def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


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

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

for a in A:
    if a == 1:
        ans += lcm
        continue
    l = lcm*pow(a, mod-2, mod)
    ans += l
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

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

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


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

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

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

print(ans % mod)

Submission status: Wrong Answer

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(0)

Submission status: Wrong Answer

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

a=A[0]
for b in A:
    a = a /fractions.gcd(a, b)*b

count=0
for i in A:
    count+=a//i

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

Submission status: Wrong Answer

Solution code:
def gcd(n,m):
  if n>m:
    return gcd(m,n);
  if n==0:
    return m;
  return gcd(m-n*(m//n),n)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
  
n=int(input())
a=list(map(int,input().split()))
s=1
for i in a:
  s=lcm(s,i)
ans=0
for i in a:
  ans+=s//i
  ans % 1000000007
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce

mod = 10**9 + 7

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

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

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

print(ans)

Submission status: Wrong Answer

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 % MOD // a % MOD for a in a_ls]
print(sum(ls) % MOD)

Submission status: Wrong Answer

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

def func(x):
    if x <= 1:
        return []
    for i in range(2,int(x**0.5)+1):
        if x%i == 0:
            count = 0
            while x%i==0:
                x //= i
                count += 1
            return [[i,count]]+func(x)
    return [[x,1]]
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = [0]*(10**6)
for i in A:
    for a,b in func(i):
        lcm[a] = max(lcm[a],b)
L = 1
for i in range(2,10**6):
    L *= pow(i,lcm[i],MOD)
    L %= MOD
ans = 1
for i in A:
    ans += L*pow(i,MOD-2,MOD)
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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 % MOD

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

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce
from decimal import Decimal

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

x = lcm(a)
ans = 0

Submission status: Wrong Answer

Solution code:
# import itertools
# import math
import fractions

MOD = 10 ** 9 + 7


def solve(N, A):
    lcm_ans = A[0]
    for i in range(1, N):
        lcm_ans = lcm_ans * A[i] // fractions.gcd(lcm_ans, A[i])

    ans = 0
    for AA in A:
        ans += lcm_ans // AA

    return ans // MOD


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

# P = []
# S = []
# for i in range(N):
#     pp, ss  = map(int, input().split())
#     P.append(pp)
#     S.append(ss)

print(solve(N, A))

Submission status: Wrong Answer

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])
cnt=0
for i in range(n):
  cnt+=ans//a[i]
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 19 21:14:43 2020

@author: masat
"""
import fractions

N = int(input())

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

A_list_2 = []
for i in A_list:
    if i % A_list[0] == 0:
        A_list_2.append(i//A_list[0])
    else:
        A_list_2.append(i)

GCD = 1
LCM = 1
for i in A_list_2:
    GCD = fractions.gcd(GCD,i)
    LCM = (LCM*i)//GCD

Bmax = LCM * A_list[0]

answer = 0

for i in A_list:
    answer += Bmax//i

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

Submission status: Wrong Answer

Solution code:
# import itertools
# import math
import fractions

MOD = 10 ** 9 + 7


def solve(N, A):
    lcm_ans = A[0]
    for i in range(1, N):
        lcm_ans = lcm_ans * A[i] // fractions.gcd(lcm_ans, A[i])

    ans = 0
    for AA in A:
        ans += lcm_ans // AA

    return ans


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

# P = []
# S = []
# for i in range(N):
#     pp, ss  = map(int, input().split())
#     P.append(pp)
#     S.append(ss)

print(solve(N, A))

Submission status: Wrong Answer

Solution code:
N = int(input())

def check(a, b, i):
  if (a + 1) * 10 ** i + b - 10 <= N:
    return 10 ** (i - 1)
  else:
    ret = 0
    for j in range(10 ** (i - 1)):
      if a * 10 ** i + j * 10 + a <= N:
        ret += 1
      else:
        return ret
ans = 0
for a in range(1, 10):
  for b in range(1, 10):
    if a == b:
      n = 0
      if a * 10 + b <= N:
        n += 2
      elif a <= N:
        ans += 1
      for i in range(2, 6):
        n += check(a, b, i)
      ans += n ** 2
    else:
      n, m = 0, 0
      if a * 10 + b <= N:
        n += 1
      if b * 10 + a <= N:
        m += 1
      for i in range(2, 6):
        n += check(a, b, i)
        m += check(b, a, i)
      ans += n * m
print(ans)

Submission status: Wrong Answer

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

C = list(set(A))

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

def gcdd(numbers):
    return reduce(gcd, numbers)

def lcm_base(x, y):
    return (x * y) // 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())
a=list(map(int,input().split()))
# import numpy as np
lcmn = lcm_list(a)
ans = 0
for i in range(n):
    ans += (lcmn // a[i])  % (10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
n = int(input())
m = 1000000007
l = list(map(int,input().split()))
a,v=1,1
for i in l:
    b = fractions.gcd(a,i)
    a = ((a*i)%m)*(pow(b,m-2,m))%m

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

lcmall = A[0]

for a in A:
    lcmall = lcm(a, lcmall)
    if lcmall == 1:
        break

A.insert(0, 1)
A.insert(0, 1)
A.append(1)
A.append(1)

ans = 0
R = int(1e9) + 7

for i in range(2,n+2):
    ans += A[i-2]*A[i-1]*A[i]*A[i+1]*A[i+2] // lcmall**5
    if ans > R:
        ans = ans % R

print(ans)

Submission status: Wrong Answer

Solution code:
# Hello World program in Python
def gcd(a,b):
    if not b: return a
    return gcd(b,a%b)
def lcm(a, b):
    return (a*b) //gcd(a, b)
N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007
for x in A:
    l = lcm(l, x) % mod
for x in A:
    ans = (ans + l/x) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
# import math
import functools
import fractions


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

    L = functools.reduce(lcm, A)


    C = [L // a for a in A]

    print(sum(C))



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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 1000000007

def gcd(a, b):
    while b:
        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()))

g = a[0]
l = 1

for i in a[1:]:
    g = gcd(g, i)

for i in range(n):
    a[i] //= g

for i in a:
    l *= i

s = 0

for i in a:
    s = (s + l // i) % MOD

print(s)

Submission status: Wrong Answer

Solution code:
import fractions
from functools import reduce

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

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

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

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

x = lcm_list(a)
ans = 0

for i in a:
    ans += (x//i)
    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()))

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


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

print(sums)

Submission status: Wrong Answer

Solution code:
# import math
import functools
import fractions


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

    L = functools.reduce(lcm, A)

    print(L)

    C = [L // a for a in A]

    print(sum(C))



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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

C = list(set(A))

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

MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += lcm // a
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table
mod=10**9+7
it=inverse_table(10**6,mod)
n=int(input())
a=sorted(list(map(int,input().split())))
use=[]
for i in range(n):
    for j in range(i+1,n):
        if a[j]%a[i]==0:
            break
    else:
        use.append(a[i])
use=use[:-1]
if len(use)==0:
    use=[1]
v=1
for e in use:
    v=v*e%mod
ans=0
mx=max(a)
for i in range(n):
    ans=(ans+((mx*v%mod)*it[a[i]])%mod)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
import math
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 = input(int())
a_list = list(map(int,input().split()))
min_baisu = lcm_list(a_list)
b_list = []
for i in a_list:
  b_list.append(min_baisu // i)
print(sum(b_list) % (10**9 + 7))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

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

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

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

lcmn = lcm(A)

ans = 0
for i in range(len(A)):
    if i % 3 == 0:
        ans += (lcmn // A[i]) % mod

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

Submission status: Wrong Answer

Solution code:
#coding:utf-8

import fractions
from functools import reduce

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

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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


ans = 0
sumv = 1
    
sumv = gcd_list(a)
for num in a:
    ans += num // sumv
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

#https://qiita.com/maebaru/items/317af98e85e9f4db04f9
def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = 2
    while n <= m:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return list(primes)
    
#https://qiita.com/snow67675476/items/e87ddb9285e27ea555f8
def factorization(n,primes,primenum_count_for_lcm):
    temp = n
    for i in range(len(primes)):
        if temp%primes[i]==0:
            cnt=0
            while temp%primes[i]==0:
                cnt+=1
                temp //= primes[i]
            if primenum_count_for_lcm[i] < cnt:
                primenum_count_for_lcm[i] = cnt
        if temp < primes[i]:
            break

    if temp!=1:
        if 10**3<temp:
            primes.append(temp)
            primenum_count_for_lcm.append(1)
        else:    
            idx = primenum_count_for_lcm.index(temp)
            if primenum_count_for_lcm[idx] == 0:
                primenum_count_for_lcm[idx] = 1
            
    #if arr==[]:
    #    arr.append([n, 1])
    
    return primenum_count_for_lcm

primes = prime_numbers(int(10**3))
primes.sort()
primenum_count_for_lcm = [0]*len(primes)
for i in range(N):
    primenum_count_for_lcm = factorization(A[i],primes,primenum_count_for_lcm)

sugoilcm = 1
for i in range(len(primes)):
    sugoilcm *= primes[i]**primenum_count_for_lcm[i]

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

def gcd1(a, b):
    def calc(a, b, first, second):
        if a < b:
            a, b = b, a
        r = a % b
        q = -(a - r)//b
        if r == 0:
            return b, second
        # first += q * second
        first = [x + q * y for (x, y) in zip(first, second)]
        return calc(r, b, second, first)
    first = [1, 0]
    second = [0, 1]
    return calc(a, b, first, second)

def mod_inv(n, mod):
    table = gcd1(n, mod)
    inv = table[1][1]
    if inv < 0:
        inv += mod
    return inv

m = 10**9 + 7
d = 1
l = 1
for i in range(N):
    a = A[i]
    l = (l * a) % m
    for j in range(i + 1, N):
        b = A[j]
        d = (d * gcd(a, b)) % m

l = (l * mod_inv(d, m))
# print(d)
ans = 0
for a in A:
    i = mod_inv(a, m)
    b = l * i
    # print(a, i, b, d)
    # print(a * i % m)
    ans = (ans + b) % m
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

lcmall = A[0]

for a in A:
    lcmall = lcm(a, lcmall)
    if lcmall == 1:
        break

A.insert(0, 1)
A.insert(0, 1)
A.append(1)
A.append(1)


ans = 0
R = int(1e9 + 7)

# 5つ組でみていくのか？
for i in range(2,n+2):
    ans += A[i-2]*A[i-1]*A[i]*A[i+1]*A[i+2] / lcmall
    if ans > R:
        ans = ans % R

print(ans)

Submission status: Wrong Answer

Solution code:

    
P = 10**9 + 7
N = 1000001
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

n = int(input())
lili = list(map(int,input().split()))
import copy
lili2 = copy.copy(lili)
#a>b
inin = 1
lili = list(set(lili))
for i in range(2,10 ** 3 +2):
    count = 0
    for j in range(len(lili)):
        if lili[j] % i != 0: continue
        now = 0
        while (lili[j] % i == 0):
            now += 1
            lili[j] = lili[j] // i
        count = max(count,now)
    inin = inin * (i ** count) % P
for i in range(len(lili)):

    inin = inin * lili[i] %P

ans = 0
for i in range(n):
    ans += inin * inv_t[lili2[i]] %P
    ans % P
print(ans %P)

Submission status: Wrong Answer

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

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

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

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

def lcm (x,y):
  return div(mul(x, y), gcd(x, y))

def add(a, b):
    return (a + b) % mod

p = A[0]
for a in A[1:]:
  p = lcm(p, a)

ans = 0
for a in A:
  ans = add(ans, div(p, a))
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

d = defaultdict(int)


def prime_factorization(n):  # 素因数分解
    res = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            res.append((i, cnt))
    if n > 1:
        res.append((n, 1))
    return res


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

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

for a in A:
    if a == 1:
        ans += lcm
        continue
    pf = prime_factorization(a)
    l = lcm
    for k, v in pf:
        x = pow(k, v, mod)
        l *= pow(x, mod-2, mod)
        l %= mod
    ans += l
    ans %= mod

print(ans % mod)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
import functools
def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def multiple(a, b):
    return a*b // euclid(a, b)
def lcm(nums):
        return functools.reduce(multiple, nums)

if __name__ == "__main__":
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    ll = lcm(A)
    ans = 0
    for a in set(A):
        ans += (ll//a)%mod
        ans %= mod
    print(int(ans))