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: Accepted

Solution code:
# 参考：jj1guj，https://atcoder.jp/contests/abc152/submissions/9630014

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

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

N=int(input())
A=list(map(int,input().split()))
a_lcm=A[0]

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

a_lcm%=1000000007

result=0
for i in range(N):
    result+=(a_lcm*pow(A[i],1000000007-2, 1000000007))%1000000007
print(result%1000000007)

Submission status: Accepted

Solution code:
import math
import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

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

#最小公倍数
def union_lcm(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=num*lists[i]//fractions.gcd(num,lists[i])
        return num


#最大公約数
def union_gcd(lists):
    if len(lists)==1:
        return lists[0]
    elif len(lists)>1:
        num=lists[0]
        for i in range(1,len(lists)):
            num=fractions.gcd(num,lists[i])
        return num
mod=10**9+7   
n=int(input())
lists=list(map(int,input().split()))
a=union_lcm(lists)
c=0
a=a%mod
for i in range(n):
    c+=a*modinv(lists[i],mod)
    c=c%mod
print(c)

Submission status: Accepted

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


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

L = 1

D = 1000000007
for i in range(N):
    L = lcm(L,A[i]) 
L = L % D

res = 0
for i in range(N):
    res = (res + L * pow(A[i],D-2,D)) % D  
print(int(res))

Submission status: Accepted

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

import fractions

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

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

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

b = 0

for i in A:
##    b += lcm_list(A)/i
    b += ans//i
print(int(b)%(10**9+7))

Submission status: Accepted

Solution code:
import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a * inv(x, mod) for x in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

L = reduce(lambda x, y: x * y // gcd(x, y), A)

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

Submission status: Accepted

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

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*pow(i,MOD-2,MOD)

print(ans%MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

# lcmTotal = 1
# for i in numList:
#   lcmTotal = lcm_base(lcmTotal, i)

lcmTotal = lcm_list(numList)

result = 0
for targetNum in numList:
  result += lcmTotal // targetNum

print(result % mod)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import fractions

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

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


num = 1
for i in nums:
    num = lcm(num, i)
print(sum([num // i for i in nums]) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
print(ans%(10**9+7))

Submission status: Accepted

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 in prime:
            if p in tmpdic: tmpdic[p]+=1
            else: tmpdic[p]=1
        else: zz.add(x)

    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*p)%MOD

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

Submission status: Accepted

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

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

def saisho_ko_baisu(A,B):
    # A < B
    if B < A:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort()
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    tmp = saisho_ko_baisu(tmp, A[i])
res = 0
for a in A:
    res += tmp//a

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n=int(input())
A=list(map(int,input().split()))
def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a
    
def lcm(m,n):
    return (m*n)//gcd(m,n)
for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    count+=pro//ai
print(count%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l_1 = 1
l_2 = 1
mod = 10**9+7
def lcm(x,y):
    return x*y//gcd(x,y)
for i in A[:N//2]:
    l_1 = lcm(l_1,i)
for j in A[N//2:]:
    l_2 = lcm(l_2,j)
l = lcm(l_1,l_2)
out1 = sum([l_1//i for i in A[:N//2]])
out2 = sum([l_2//i for i in A[N//2:]])
out1 *= l//l_1
out2 *= l//l_2
print((out1+out2)%mod)

Submission status: Accepted

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

MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
lcm = 1
for i in A:
    lcm = (lcm*i)//gcd(lcm,i)
ans = 0
for i in A:
    ans += lcm//i
print(ans%MOD)

Submission status: Accepted

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


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


MOD = 1000000007

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

l = 1
for i in range(n):
    l = LCM(l, a[i])

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

Submission status: Accepted

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 = 1
for i in range(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: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 10 ** 9 + 7
def gcd(a, b):
    if b ==0:
        return a
    else:
        return gcd(b,a%b)

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

k = 0
for j in a:
    k +=  mk // j
print(k %MOD)

Submission status: Accepted

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

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

lcm = 1
s = 0
for i in range(N):
    k = l[i]
    g = gcd(k,lcm)
    t = k//g
    lcm = lcm*t
    s = s*t + lcm//k
print(s%u)

Submission status: Accepted

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', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N=I()
    A=LI()
    l = 1
    for a in A:
        l *= a//gcd(l,a)
    ans = 0
    l = ModInt(l)
    for a in A:
        ans += l/a
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

P = int(1e9)+7
n = int(input())

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

print(sum(ans)%div)

Submission status: Accepted

Solution code:
def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()

Submission status: Accepted

Solution code:
from fractions import gcd

MOD = 1000000007

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

lcm = 1
for i in A: lcm = lcm * i // gcd(lcm, i)

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

print(ans % MOD)

Submission status: Accepted

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', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    N=I()
    A=LI()
    l = 1
    for a in A:
        l *= a//gcd(l,a)
    ans = 0
    for a in A:
        ans += ModInt(l)/a
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

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

def lcm_list(l):
    lcm = l[0]
    for i in range(len(l)):
        lcm = lcm*l[i] // gcd(lcm, l[i])
    return lcm

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

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

mod = 10**9 + 7

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


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

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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


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

N=int(input())
A=list(map(int,input().split()))
MOD=(10**9)+7
S=list(set(A))
LCM=lcm_list(S)
ans=0

for i in range(N):
    ans+=(LCM//A[i])


print(ans%MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

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

def lcm(numbers):
    t = 1
    for n in numbers:
        t = lcm_base(t, n)
    return t

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

mod = 10**9+7
ans = 0
t = lcm(A)
t %= mod
for i in range(N):
    ans = (ans + t*pow(A[i],mod-2, mod))%mod

print(ans)

Submission status: Accepted

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
a=0
for j in t:
  a+=ans//j
print(int(a)%mod)

Submission status: Accepted

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


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: Accepted

Solution code:
from fractions import gcd

MOD = 1000000000 + 7

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

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))

Submission status: Accepted

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()))
s=1
for i in a:
  s=lcm(s,i)
ans=0
for i in a:
  ans+=s//i
print(ans % 1000000007)

Submission status: Accepted

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

MOD=10**9+7

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

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

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

Submission status: Accepted

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

N = int(input())

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

L = reduce((lambda x, y: x // gcd(x, y) * y), A)

res = 0

MOD = 10**9+7

for a in A:
  res += L//a

print(res%MOD)

Submission status: Accepted

Solution code:
import sys

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


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

#from math import gcd
from fractions import gcd

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


if __name__ == "__main__":
	main()

Submission status: Accepted

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)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


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

l = A[0]
for a in A:
  t = l%a
  if t != 0:
    l = lcm(l, a)

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
 
def p_prime(n): 
    prime = [2]
    for i in range(3,n+1):
        flag = 0
        for j in prime:
            if i%j == 0:
                flag = 1
                break
            if i**0.5 < j:
                break
        if flag == 0:
            prime.append(i)
    return prime

prime = p_prime(int(mod**0.5+1))
def soinsuu(M):
    a = {}
    for p in prime:
        count = 0
        while M%p ==0:
            count += 1
            M //= p
        if count > 0:
            a[p] = count
    if M != 1:
        a[M] = 1
    return a

from collections import defaultdict
AA = defaultdict(int)

for i in range(N):
    tmp = soinsuu(A[i])
    for j in tmp:
        AA[j] = max(AA[j], tmp[j])
        
L = 1
for i in AA:
    L *= pow(i,AA[i],mod)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from fractions import gcd
from functools import reduce

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
    #[x,y]
    return [w[0],w[1]]
# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

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

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

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))
 
lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = ans*(lcm_//lcm)
  ans = (ans + (lcm_//a_list[i]))
  lcm = lcm_

print(ans%MOD)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

mod = 10 ** 9 + 7

l = lcm_list(A)

ans = 0

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

ans = ans % mod

print(ans)

Submission status: Accepted

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 = lcm(x, A[i]) 


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

print(sums % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce 
def lcm_base(x, y):
  return(x * y) // gcd(x, y)
def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

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

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

Submission status: Accepted

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

Submission status: Accepted

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] = max(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: Accepted

Solution code:
from fractions import gcd
def find(a):
    ans = a[0]
    for i in range(1,len(a)):
        ans = ((ans)//(gcd(ans,a[i])) * a[i])
    return ans            
	


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

lcm = find(a)
ans = 0
mod = pow(10,9)+7
for i in a:
	ans = ans + lcm//i
	
print(ans%mod)

Submission status: Accepted

Solution code:
# 提出 #9630459

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

Submission status: Accepted

Solution code:

import fractions as fr
import functools as ft
#import math as fr


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // fr.gcd(a, lcm_)
#    print(lcm_)
    
#ans = 0
#for a in an:
#    ans += lcm_ // a
#    ans = ans % prime if ans >= prime else ans

ans = ft.reduce(lambda x,y: (x + lcm_//y), an ,0 )

print(ans%prime)

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
import math
import fractions

MOD = 1000000007

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

mod = 1000000007


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):
    x = extgcd(a,MOD)[0]
    return (MOD+x%MOD)%MOD


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


all = Counter()
for i in range(N):
    li = prime_factorize(A[i])
    tmp = Counter(li)
    for k, v in tmp.items():
        if all[k] < v:
            all[k] = v

# print(all)
lsm = 1
for k, v in all.items():
    lsm = lsm*(k**v)%MOD
# print(lsm)

ans = 0
for i in range(N):
    ans = (ans + lsm * mod_inv(A[i])) % MOD

print(ans)