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:


def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a


n = map(int, raw_input().split())
a = map(int, raw_input().split())

lcm = 1
cnt = 0
MOD = int(1e9 + 7)

for x in a:
    lcm = x*lcm/gcd(lcm, x)
    
for x in a:
    cnt += lcm/x 
    
print cnt % MOD

Submission status: Accepted

Solution code:
def main():
    from functools import reduce

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

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

    mod = 10 ** 9 + 7

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

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + pow(x, mod - 2, mod)) % mod
    ret = ret * L % mod
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''
'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''
'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  # 和集合
print(list(set(a) & set(b)))  # 積集合
'''
'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''
'''
.append(要素)
.extend(要素)
.insert(場所,要素)
del 配列名[場所]
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
'''
copy.copy(配列名)
'''
'''
sort()
sorted(reverse=true)
'''
'''
2分探索
bisect.bisect_left(リスト, 要素)
'''
'''
リスト同士の演算
list(map(lambda x, y: x+y, el2, el3))
'''
'''
配列の初期化
配列名=[a]*n+[b]*m
'''
'''
重複
list(set())
２次元配列
list(map(list, set(map(tuple, addition))))
'''
'''
順列
for el in itertools.permutations(配列のパターン):
'''
'''
Decimal()
'''
# 入力 =stdin.readline().rstrip()
# 分割 = stdin.readline().rstrip().split()




from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul
def gcd(*numbers):
    return reduce(math.gcd, numbers)


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


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


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


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


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


N = int(stdin.readline().rstrip())
A = [int(s) for s in stdin.readline().rstrip().split()]
res = lcm(A)
part = 0
for k in range(len(A)):
    part += res//A[k]
print(part % (10**9+7))

Submission status: Accepted

Solution code:
import fractions

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

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

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

MOD = 10**9+7

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

res = 0

def modulo(x, y):
  tmp = x % y
  if tmp < 0: tmp += y
  return tmp

def extgcd(x, y):
  if x < y:
    a, b = extgcd(y, x)
    return b, a
  if y == 0 or x % y == 0: return 0, 1
  a, b = extgcd(y, modulo(x , y))
  return (b, -(x // y) * b + a)

def inv(x):
  a, _ = extgcd(x,MOD)
  return modulo(a, MOD)

for a in A:
  res = (res + L* inv(a) % MOD) % MOD

print(res)

Submission status: Accepted

Solution code:
#import math
#from functools import reduce
from fractions import gcd
#from functools import lru_cache


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

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


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 = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))

Submission status: Accepted

Solution code:
import fractions

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

l = a[0]
for i in range(1, n):
    l = l * a[i] // fractions.gcd(l, a[i])

count = 0


for i in a:
  count += l//i
count %= (10**9+7)

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

mod = 10 ** 9 + 7

def prime_factor(x) :
  ret = dict()
  if x % 2 == 0 :
    ret[2] = 0
    while x % 2 == 0 :
      x //= 2
      ret[2] += 1
          
  i = 3
  while i * i <= x :
    if x % i == 0 :
      ret[i] = 0
      
      while x % i == 0 :
        x //= i
        ret[i] += 1
    i += 2
      
  if x != 1 :
    ret[x] = 1
  
  return ret

pr = defaultdict(int)
for i in range(N) :
  for k, v in prime_factor(A[i]).items() :
    pr[k] = max(pr[k], v)
    
a = 1
for k, v in pr.items() :
  a *= pow(k, v, mod)
  a %= mod

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

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

saikou = lcm_list(a)
ans = 0

for i in a:
  b = saikou // i
  ans += b
  
print(int(ans) % 1000000007)

Submission status: Accepted

Solution code:
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(a, b):
    return a * b // gcd(a, b)


if len(A) < 2:
    print(1)
    exit()

if A[0] < A[1]:
    temp = lcm(A[1], A[0])
else:
    temp = lcm(A[0], A[1])

for i in range(2, N):
    if temp < A[i]:
        temp = lcm(A[i], temp)
    else:
        temp = lcm(temp, A[i])

if temp == A[0]:
    print(N)
    exit()

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

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

Submission status: Accepted

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

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

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

def list_lcm(l):
    return functools.reduce(lcm,l)

g = list_lcm(A)

B = [g //a for a in A]
print(sum(B) % MOD)

Submission status: Accepted

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

def solve(arr):
    ab = lcm(arr)
    sum = 0
    for a in arr:
        sum += ab // a
    return sum % (10**9+7)

n = int(input())
arr = list(map(int, input().split()))
print(solve(arr))

Submission status: Accepted

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

def pow_mod(x,n):
    if n==0:
        return 1
    
    K = 1
    while n>1:
        if n%2 != 0:
            K *= x
            K %= mod
        x *= x
        x %= mod
        n //= 2

    return K*x

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

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

Gcd = gcd(A[0],A[1])
ans = (A[0]//Gcd+A[1]//Gcd)%mod
temp = A[0]//Gcd

for i in range(1,N-1):
    #Gcd = lcm(A[i],A[i+1])
    Gcd = gcd(A[i],A[i+1])
    #temp2 = Gcd//A[i]
    temp2 = A[i+1]//Gcd
    #Gcd2 = lcm(temp,temp2)
    Gcd2 = gcd(temp,temp2)

    #a = Gcd2//temp
    a = temp2//Gcd2
    #b = Gcd2//temp2
    b = temp//Gcd2

    temp = A[i]//Gcd*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod


    Gcd %= mod #注意
    c = A[i]
    c %= mod
    d = c*pow_mod(Gcd,mod-2)
    #d = Gcd//c
    d %= mod


    e = b*d%mod
    ans += e
    #ans += Gcd//A[i+1]*b
    ans %= mod


print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from math import log,ceil
from fractions import gcd
mod = 10**9 + 7


def euclid(a:int,b:int)->(int,int):
    #return x,y s.t ax + by = gcd(a,b)
    #a > b >= 0
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    #gcd(p,b) == 1
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    #a // b
    x = inverse(b,mod)
    return  (a*x)%mod



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

def main():
    N = int(input())
    A  =list(map(int,input().split()))
    neko = 1
    for a in A:
        neko = lcm(neko,a)
    sm = 0
    neko = neko%mod
    for a in A:
        sm = (sm + devide_mod(neko , a,mod))%mod
    print(sm)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import reduce
import fractions


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


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


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


n = int(input())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % int(1e9+7)
print(ans)
# print(l)
# print(a)

Submission status: Accepted

Solution code:

from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    #res%=mod
print(res%mod)

Submission status: Accepted

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


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

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


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

ans = 0
inv_sum = 0
l = A[0]
for a in A:
    l = lcm(l, a)
    inv_sum = (inv_sum + mod_inverse(a)) % mod
print(l * inv_sum % mod)

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)

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

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=inv_t[ai]
    ans%=mod
print((pro*ans)%mod)

# pro2=1
# for ai in A:
#     pro2=(pro2*ai)%mod
#     pro=gcd(pro,ai)
# for ai in A:
#     count+=pro//ai
#     count%=mod
# print(count)

Submission status: Accepted

Solution code:
import functools

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

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

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

def lcm_list(nums):
        return functools.reduce(lcm, nums)

lcm_a = lcm_list(a)

b = [lcm_a//a[i] for i in range(n)]

print(sum(b) % ((10**9)+7))

Submission status: Accepted

Solution code:
import collections
import sys

readline = sys.stdin.buffer.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
    print(ans % C)


main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7

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

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

l = lcm(a)
total = 0

for a_ in a:
    total += l // a_

print(total % MOD)

Submission status: Accepted

Solution code:
#  --*-coding:utf-8-*--

MOD = 10**9 + 7

def getPrimes(n):
    if (n < 2):
        return []

    flags = [False]*(n+1)
    primes = [2]

    for p in range(3, n+1, 2):
        if not flags[p]:
            primes.append(p)
            for k in range(p**2, n+1, p):
                flags[k] = True

    return primes


def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)


def getFactors(x):
    factors = {}
    for p in P:
        if x < 2:
            break

        n = 0
        while x%p == 0:
            x //= p
            n += 1

        if n > 0:
            factors[p] = n

    if x > 1:
        factors[x] = 1

    return factors


P = getPrimes(1000)

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

maxFacts = {}

for a in A:
    facts = getFactors(a)
    for p in facts:
        if not p in maxFacts or maxFacts[p] < facts[p]:
            maxFacts[p] = facts[p]

lcd = 1
for p in maxFacts:
    lcd = lcd * modPow(p, maxFacts[p], MOD)%MOD

lcd %= MOD

s = 0
for a in A:
    s += lcd*getModInv(a, MOD)%MOD

print(s%MOD)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    l%=MOD
    ans=0
    for x in A:
        ans+=l*modinv(x,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def extgcd(a,b): #互いに素なa,bについて、a*x+b*y=1の一つの解
    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]]

def mod_inv(a,mod): # (x/a)%MODをしたい時は x%MOD * mod_inv(a,MOD)%MOD
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod


# def gcd(a, b):
#     if b == 0:
#         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()))

lcm_ = a[0]
for i in range(1, n):
    lcm_ = lcm_ * a[i] // fractions.gcd(lcm_, a[i])

# lcm_ = a[0]
ans = 0
for i in range(0,n):
    # if lcm_ % a[i] != 0:
    #     lcm_new = lcm(lcm_, a[i])
    #     ans = ans*(lcm_new%MOD *mod_inv(lcm_,MOD)%MOD)
    #     lcm_ = lcm_new

    ans += lcm_%MOD * mod_inv(a[i], MOD)%MOD

print(ans%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
lim=10**9+7
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)


n=int(input())
A=[int(i) for i in input().split()]
A_inv = [pow(a,lim-2,lim) for a in A]

Z = A[0]
k=1
for i in range(1, n):
    Z = Z // gcd(Z, A[i]) * A[i]
ans=0

Z=Z % lim
for i in range(n):
    ans = ( ans + Z*A_inv[i] ) % lim
print(ans)

Submission status: Accepted

Solution code:
MAX = 1000001

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict()

# function to return a^n

def power(a, n):

    if n == 0:
        return 1
    p = power(a, n // 2) % mod
    p = (p * p) % mod

    if n & 1:
        p = (p * a) % mod
    return p

# function to find the smallest prime
# factors of numbers upto MAX


def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

# function to return the LCM modulo M


def lcmModuloM(arr, n):

    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:

        # LCM is product of primes to their
        # higest powers modulo M
        ans = (ans * power(i, max_map[i])) % mod
    return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)


def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

# Driver code
sieve()

# python > pypy
MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())
al = list(map(int, input().split()))
MOD = 10**9 + 7

# aのmod Mでの逆元
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t*v
        u,v = v,u
    u %= m
    if u<0:
        u += m
    return u

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

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

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)%MOD
res = 0
for a in al:
    res += l*modinv(a,MOD)
    res %= MOD

print(res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
ans = 0
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)
lc = lcm(A)
for i in range(n):
    ans += lc//A[i]
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
MOD = 1000000007


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


def modinv(a, mod=MOD):
    b = mod
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= mod
    if u < 0:
        u += mod
    return u


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


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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

def lcm(a, b):
    return a//gcd(a, b)*b
    
def inv(x):
    return pow(x, MOD-2, MOD)
    

def factorize(n):
    factors = []
    
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        
        while n%i==0:
            n //= i
            cnt += 1
    
        if cnt>0:
            factors.append((i, cnt))
    
    if n>1:
        factors.append((n, 1))
    
    return factors

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
#N = 10**4
#A = [i for i in range(10**6, 10**6-N, -1)]

L = 1
d = defaultdict(int)

for Ai in A:
    f = factorize(Ai)
    
    for n, c in f:
        d[n] = max(d[n], c)

for v, c in d.items():
    L *= v**c
    L %= MOD
    
ans = 0

for Ai in A:
    ans += L*inv(Ai)
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
def lcm(x, y):
  return (x * y) // gcd(x, y)
def ll(numbers):
  return reduce(lcm, numbers, 1)
def modinv(a):
    return pow(a,m-2,m)
n=int(input())
a=list(map(int,input().split()))
l=ll(a)
x=0
m=10**9+7
lm=l%m
for i in range(n):
  x+=(lm*modinv(a[i]))%m
  x=x%m
print(x)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions
N = int(input())
* A, = map(int, input().split())
mod = 10**9+7


def gcd(a, b):
    return int(fractions.gcd(a, b))


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


LCM = reduce(lcm, A)

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

Submission status: Accepted

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

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

num = int(input())
A = [int(s) for s in input().split()]
ans = A[0]
for i in range(1,num):
    ans = lcm(ans,A[i])
B = [ans//A[s] for s in range(num)]
print(sum(B)%(10**(9)+7))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

sm = 0
for i in a: sm += g//i
print(sm%1000000007)

Submission status: Accepted

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

count=0
for i in a:
    count+=ans//i
print(count%mod)

Submission status: Accepted

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

from functools import reduce

def gcd(x, y):
  while y:
    x , y = y, x % y
  return x

lcm = l[0]
ans = 1

for i in range(1, n):
  g = gcd(lcm, l[i])
  s = lcm // g
  t = l[i] // g
  lcm = s * t * g
  ans = (ans * t + s) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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:
mod = 10**9+7
n = int(input())
num = [ int(v) for v in input().split() ]

def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

def shave(n):
    if n < 2:
        return []
    else:
        n_root = int(n**0.5)
        candidate = [i for i in range(3, n+1, 2)]
        for i in range(3, n_root+2, 2):
            candidate = [j for j in candidate if j == i or j % i != 0]
        candidate = [2] + candidate
        return candidate

d = {}
prime_list = shave(10**3)
for i in prime_list:
    d[i] = 0

def prime_factorization(x):

    for i in prime_list:
        if x == 1:
            break
        elif x % i == 0:
            q = 0
            while x % i == 0:
                x //= i
                q += 1
            d[i] = max(d[i], q)
    if x != 1:
        d[x] = 1
    return 

for i in num:
    prime_factorization(i)

l = 1
for i in d:
    l *= pow(i, d[i], mod)
    l %= mod

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
P = 10 ** 9 + 7
p = 10 ** 9 + 7
mo = P
inv_t = [0]+[1]
for i in range(2,1000009):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#print("俺のソフト")

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

M = a[0]
for i in range(1, n):
    M = M * a[i] // gcd(M, a[i])

M = M%p
ans = 0
for i in range(n):
    ans += M*inv_t[a[i]]
    ans = ans %p

print(ans)

Submission status: Accepted

Solution code:
import fractions


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


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

Submission status: Accepted

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


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

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

mod = 10**9+7
lcm = 1
B = [0]*N

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

ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import fractions

def modinv(a, MOD=1000000007):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= (t * b)
        tmp = a
        a = b
        b = tmp
        u -= (t * v)
        tmp = u
        u = v
        v = tmp
    u %= MOD
    if u < 0:
        u += MOD
    return u
            

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

def lcm_array(x):
    value = x[0]
    for i in range(1, len(x)):
        value = lcm(value, x[i])
    return value 

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A

def solve(N, A, MOD=1000000007):
    lcmv = lcm_array(A)
    bsum = 0
    for i in range(N):
        bsum += (lcmv * modinv(A[i]) % MOD)
        bsum %= MOD
    return bsum

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))

Submission status: Accepted

Solution code:
n = int(input())

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

M = 1000000007


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

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

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

def extGCD(a,b):
    if b==0:
        return a,1,0
    d, y, x = extGCD(b, a%b)
    y -= a // b * x
    return d, x, y

def modinv(a,p):
    b, x, y = extGCD(a, p)
    return mod(x,p)


gcdval = a[0]
modpi = 1
lcmval = 1
for i in range(n):
    modpi = mod(modpi * a[i], M)
    gcdval = gcd(gcdval, a[i])
    lcmval = lcm(lcmval, a[i])

#print("GCD: {}".format(gcdval))
#print("pi: {}".format(modpi))    
#print("lcm: {}".format(lcmval))

sum = 0
for i in range(n):
    sum = sum + mod(lcmval * modinv(a[i], M), M)
    #print("{}".format(mod(lcmval * modinv(a[i], M), M)))
    sum = mod(sum, M)

print("{}".format(sum))