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:
from fractions import gcd
def lcm(x,y):
  return (x*y) // gcd(x,y)
n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7
l = a[0]
for i in range(1,n):
  l = lcm(l,a[i])
ans = 0
for i in range(n):
  ans += l//a[i]
print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
MOD = 1000000007
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

lcma={}
for ai in A:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,MOD)
  l%=MOD
ans=0
for ai in A:
  ans+=l*pow(ai,MOD-2,MOD)
  ans%=MOD

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from math import sqrt
    from fractions import gcd
    from collections import defaultdict
    from copy import deepcopy

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

    p = [1] * (1001)
    P = []  # 1000までの素数表
    p[0] = p[1] = 0
    for x in range(2, int(sqrt(1000000)) + 1):
        if p[x]:
            P.append(x)
            for y in range(x * x, 1001, x):
                p[y] = 0

    B = [defaultdict(int) for i in range(N)]  # N個の数を素因数分解したもの
    lcm = defaultdict(int)  # N個の数のlcmを素因数分解したもの

    for i in range(N):
        for j in P:
            if A[i] % j == 0:
                while A[i] % j == 0:
                    A[i] //= j
                    B[i][j] += 1
            lcm[j] = max(lcm[j], B[i][j])
        if A[i] != 1:
            B[i][A[i]] = 1
            lcm[A[i]] = 1

    l = 1  # N個の数のlcm
    for i in lcm.keys():
        l = (l * pow(i, lcm[i], mod)) % mod

    ans = 0
    # l/A[i]の和を求めていく
    for i in range(N):
        r = l
        for j in list(B[i].keys()):
            r = (r * pow(j, mod - B[i][j] - 1, mod)) % mod
        ans = (ans + r) % mod

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from fractions import gcd
from functools import reduce
input = lambda: sys.stdin.readline().strip()
MOD = 1000000007
def lcm(a, b):
    return a // gcd(a, b) * b
n = int(input())
A = [int(x) for x in input().split()]
x = reduce(lcm, A)
print(sum(x // ai for ai in A) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline().strip()

MOD = 1000000007  # type: int

def modinv(x):
    return pow(x, MOD - 2, MOD)

def solve(N: int, A: "List[int]"):
    factors = [0 for i in range(10**6 + 1)]
    for x in A:
        i = 2
        while i * i <= x:
            curr = 0
            while x % i == 0:
                curr += 1
                x //= i
            factors[i] = max(factors[i], curr)
            i += 1
        if x > 1:
            factors[x] = max(factors[x], 1)
    lcm = 1
    for i in range(10**6 + 1):
        lcm *= pow(i, factors[i], MOD)
        lcm %= MOD
    ans = 0
    for ai in A:
        ans += lcm * modinv(ai) % MOD
        ans %= MOD
    print(ans)

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod
for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  b = A[i+1] // a
  L = b * L
L %= mod
S = 0
for i in range(N):
  S += inved(A[i])
  S %= mod
S *= L
S %= mod
print(S)

Submission status: Accepted

Solution code:
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(input())
    a=list(map(int,input().split()))
    mod=pow(10,9)+7
    lcma={}
    for ai in a:
      f=factorization(ai)
      for fi in f:
        if fi[0] in lcma:
          lcma[fi[0]]=max(lcma[fi[0]],fi[1])
        else:
          lcma[fi[0]]=fi[1]
    l=1
    for k,v in lcma.items():
      l*=pow(k,v,mod)
      l%=mod
    ans=0
    for ai in a:
      ans+=l*pow(ai,mod-2,mod)
      ans%=mod
    print(ans)

main()

Submission status: Accepted

Solution code:
from fractions import gcd

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


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

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

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

input = sys.stdin.buffer.readline
mod = 10 ** 9 + 7


def modinv(a, mod):
    return pow(a, mod - 2, mod)


n = int(input())
if n == 1:
    print(1)
    exit()
A = list(map(int, input().split()))
lcm = A[0]
for i in range(n):
    g = gcd(lcm, A[i])
    lcm *= A[i] // g
ans = 0
for i in range(n):
    gyaku = modinv(A[i], mod)
    ans += lcm * gyaku
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
di = 10**9+7
##試し割り
import math
import collections
def trial_division_prime(n, prime_list,prime_count):
    tmp=collections.Counter()
    for i in prime_list:
        if i * i > n:
            break
        while n % i == 0:
            n /= i
            tmp[i] += 1
    if n > 1:
        tmp[int(n)] += 1
    for num,rui in tmp.items():
        if prime_count[num]<rui:
            prime_count[num]=rui
        else:
            continue
    return prime_count
##ふるい
import itertools
def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list

lis = eratosthenes_sieve(int(math.sqrt(max(a))+1))
prime_count = collections.Counter()
for i in a:
    cnt = trial_division_prime(i,lis,prime_count)
#print(cnt)
lcm=1
for s,t in prime_count.items():
    lcm=(lcm*pow(s,t,di))%di
#print(lcm)
su = 0
for i in a:
    div = pow(i,di-2,di)
    su = (su+(lcm*div)%di)%di
print(su)

Submission status: Accepted

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

#n=10000
#a=list(range(10**6,10**6-n,-1))

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
lcma={}
for ai in a:
  f=factorization(ai)
  for fi in f:
    if fi[0] in lcma:
      lcma[fi[0]]=max(lcma[fi[0]],fi[1])
    else:
      lcma[fi[0]]=fi[1]
l=1
for k,v in lcma.items():
  l*=pow(k,v,mod)
  l%=mod
ans=0
for ai in a:
  ans+=l*pow(ai,mod-2,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = {}
ans = 0
mod = 10**9 + 7

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

for i in a:
    arr = factorization(i)
    for j,k in arr:
        if j not in d:
            d[j] = k
        else:
            d[j] = max(k, d[j])

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import time

class Osa_k:
    def __init__(self, n):
        self.n = n
        self.min_factor = [int(x) for x in range(n+1)]
        
        self.is_prime = [True] * (self.n + 1)
        self.is_prime[0] = False
        self.is_prime[1] = False
        for j in range(4, self.n+1, 2):
            self.is_prime[j] = False
            self.min_factor[j] = 2
        for i in range(3, int(self.n**0.5) + 1, 2):
            if not self.is_prime[i]:
                continue
            for j in range(i * 2, self.n + 1, i):
                self.is_prime[j] = False
                if self.min_factor[j] >= i:
                	self.min_factor[j] = i
        


    def calculate(self, x):
        ans = []
        while x > 1:
            key = self.min_factor[x]
            while x%key == 0:
                ans.append(key)
                x //= key
        counter = Counter(ans)
        return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = dict()
    osa_k = Osa_k(max(a))
    for i in range(n):
        primes = osa_k.calculate(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
              
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    print(ans)

    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
import time

class Osa_k:
    def __init__(self, n):
        self.n = n
        self.min_factor = [int(x) for x in range(n+1)]
        
        self.is_prime = [True] * (self.n + 1)
        self.is_prime[0] = False
        self.is_prime[1] = False
        for j in range(4, self.n+1, 2):
            self.is_prime[j] = False
            self.min_factor[j] = 2
        for i in range(3, int(self.n**0.5) + 1, 2):
            if not self.is_prime[i]:
                continue
            for j in range(i * 2, self.n + 1, i):
                self.is_prime[j] = False
                if self.min_factor[j] >= i:
                	self.min_factor[j] = i
        


    def calculate(self, x):
        ans = []
        while x > 1:
            key = self.min_factor[x]
            while x%key == 0:
                ans.append(key)
                x //= key
        counter = Counter(ans)
        return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    prime_list = dict()
    osa_k = Osa_k(max(a))
    for i in range(n):
        primes = osa_k.calculate(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
              
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 <= n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 <= n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


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

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

a_fac = []
lcm_fac = defaultdict(int)
for a_i in a:
    a_fac_i = factorize(a_i)
    a_fac.append(a_fac_i)
    for k, v in a_fac_i.items():
        lcm_fac[k] = max(lcm_fac[k], v)

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

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

print(ans)

Submission status: Accepted

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

def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
def calclcm(a, b):
  return a*b//calcgcd(a, b)

r = 1
a = As[0]
for i in range(1, N):
  b = As[i]
  d = calcgcd(a, b)
  r = (r*(b//d)+(a//d))%1000000007
  a = a*b//d
print(r)

Submission status: Accepted

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

import fractions

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

ans = 0
for j in range(N):
    ans += G // A[j]

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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=reduce(lambda x,y:x//gcd(x,y)*y,a)
ans=sum(map(lambda x:l//x,a))
print(ans%mod)

Submission status: Accepted

Solution code:

class PrimeNum:
    def __init__(self, N):
        self.N = N
        [self.is_prime, self.primes, self.min_factor] = self.Eratosthenes(N)

    def Eratosthenes(self, n):
        # 素数テーブル
        is_prime = [True] * (n+1)
        is_prime[0] = False
        is_prime[1] = False

        # nを割り切る最小の素数を記録
        min_factor = [0] * (n+1)
        min_factor[1] = 1
        
        primes = []

        for i in range(2,n+1):
            if not is_prime[i]:
                continue

            primes.append(i)
            min_factor[i] = i
            for cur in range(i*2, n+1, i):
                is_prime[cur] = False
                if min_factor[cur] == 0:
                    min_factor[cur] = i
                cur += i

        return [is_prime, primes, min_factor]
    
    def PrimeFactorization(self, K):
        # Kの素因数分解を返す
        number = []
        exponent = []
        while K>1:
            ex = 0
            p = self.min_factor[K]
            while K%p==0:
                K //= p
                ex += 1
            number.append(p)
            exponent.append(ex)
        return [number, exponent]


N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7
# 素因数分解の形でLCMを求める

Prime = PrimeNum(max(A))
lcm_e = [0]*(max(A)+1)
for i in range(N):
    nums,exs = Prime.PrimeFactorization(A[i])
    for n,e in zip(nums,exs):
        lcm_e[n] = max(lcm_e[n], e)

LCM = 1
for i in range(len(lcm_e)):
    if lcm_e[i] != 0:   
        LCM *= pow(i, lcm_e[i], MOD)
        LCM %= MOD
ans = 0
for a in A:
    ans += LCM * pow(a, MOD-2, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    d = {}

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            if cnt:
                d[i] = max(d.get(i,0),cnt)
            if x == 1: break
        else:
            d[x] = max(d.get(x,0),1)
    m = 1
    for i,x in d.items():
        m = (m * i ** x) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    d = {}

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            if cnt:
                if i in d:
                    d[i] = max(d[i],cnt)
                else:
                    d[i] = cnt
            if x == 1: break
        else:
            if x in d:
                d[x] = max(d[x],1)
            else:
                d[x] = 1
    m = 1
    for i,x in d.items():
        m = (m * i ** x) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    A = LI()
    d = [0] * (max(A)+1)

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            d[i] = max(d[i],cnt)
            if x == 1: break
        else:
            d[x] = max(1,d[x])
    m = 1
    for i in range(2,len(d)):
        m = (m * i ** d[i]) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections as col

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i ; ans.append(i)
    if n != 1: ans.append(n)
    return col.Counter(ans)
    
n = int(input())
a = list(map(int,input().split()))

cnt = col.Counter()
for num in a:
    new = prime(num)
    for key,val in new.items():
        if val > cnt[key] : cnt[key] = val

LCM = 1
MOD = 10**9 + 7
for key,val in cnt.items(): LCM *= key**val %MOD

ans = 0
for num in a:
    b = LCM * pow(num, MOD-2, MOD) #割るのではなく逆元をかける
    ans += b
    
print(ans%MOD)

Submission status: Accepted

Solution code:
import collections as col

def prime(n):
    ans = []
    num = n
    for i in range(2, int(n**0.5)+1):
        while not num%i: num //= i ; ans.append(i)
    if num != 1: ans.append(num)
    return col.Counter(ans)
    
n = int(input())
a = list(map(int,input().split()))

cnt = col.Counter()
for num in a:
    new = prime(num)
    for key,val in new.items():
        if val > cnt[key] : cnt[key] = val

LCM = 1
MOD = 10**9 + 7
for key,val in cnt.items(): LCM *= key**val %MOD

ans = 0
for num in a:
    b = LCM * pow(num, MOD-2, MOD) #割るのではなく逆元をかける
    ans += b
    
print(ans%MOD)

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
mod = int(1e+9+7)
max_val = int(1e+6+1)

def make_kago(x):
    kago = [0 for _ in range(x+1)]
    sosuu = []
    for i in range(2,x+1):
        if kago[i] != 0:
            continue
        sosuu.append(i)
        for j in range(i, x+1, i):
            if kago[j] == 0:
                kago[j] = i
    return kago, sosuu

kago, sosuu = make_kago(max_val)

def prime_factorization(x):
    if x==0 or x==1:
        return None
    soinsuu = []
    while x!=1:
        soinsuu.append(kago[int(x)])
        x = x/kago[int(x)]
    
    soinsuu_dict = dict()
    for i in range(len(soinsuu)):
        if soinsuu[i] not in soinsuu_dict:
            soinsuu_dict[soinsuu[i]] = 1
        else:
            soinsuu_dict[soinsuu[i]]+=1
    return soinsuu_dict
#%%
max_soinsuu = [0 for _ in range(int(1e+6+1))]

#%%

for i in range(n):
    soinsuu_dict = prime_factorization(a[i])
    if soinsuu_dict == None:
        continue
    for k, v in soinsuu_dict.items():
        if max_soinsuu[k] < v:
            max_soinsuu[k] = v

lcm = 1
for i in range(max_val):
    if max_soinsuu[i] != 0:
        lcm = (lcm*i**max_soinsuu[i])%mod

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

Submission status: Accepted

Solution code:
from math import gcd

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

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


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


print(ans % MOD)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

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)

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

Submission status: Accepted

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


def sieve(n):
    n += 1
    res = [i for i in range(n)]
    for i in range(2, int(n**.5)+1):
        if res[i] < i:
            continue
        for j in range(i**2, n, i):
            if res[j] == j:
                res[j] = i
    return res


U = max(A)+1
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(lambda: 0)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


pf = defaultdict(lambda: 0)

for a in A:
    for p, q in prime_factor(a).items():
        if pf[p] < q:
            pf[p] = q

x = 1
for p, q in pf.items():
    x *= pow(p, q, MOD)
x %= MOD

print(sum(x*pow(a, MOD-2, MOD) for a in A) % MOD)

Submission status: Accepted

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


def sieve(n):
    res = [i for i in range(n)]
    for i in range(2, int(n**.5)+1):
        if res[i] < i:
            continue
        for j in range(i**2, n, i):
            if res[j] == j:
                res[j] = i
    return res


U = 10**6+1
min_factor = sieve(U)


def prime_factor(n):
    res = defaultdict(lambda: 0)
    while 1 < n:
        res[min_factor[n]] += 1
        n //= min_factor[n]
    return res


pf = defaultdict(lambda: 0)

for a in A:
    for p, q in prime_factor(a).items():
        if pf[p] < q:
            pf[p] = q

x = 1
for p, q in pf.items():
    x *= pow(p, q, MOD)
x %= MOD

print(sum(x*pow(a, MOD-2, MOD) for a in A) % MOD)

Submission status: Accepted

Solution code:
from functools import reduce
MOD = 10**9+7
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))


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

Submission status: Accepted

Solution code:
from functools import reduce
MOD = 10**9+7
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)


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

Submission status: Accepted

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


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    return retval


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


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


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

Submission status: Accepted

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


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    return retval


x = defaultdict(int)
for a in A:
    for p, q in factorization(a):
        if x[p] < q:
            x[p] = q

mod_x = 1
for p, q in x.items():
    mod_x *= pow(p, q, MOD)
mod_x %= MOD

B = [mod_x*pow(a, MOD-2, MOD) % MOD for a in A]
print(sum(B) % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

ans = 0
for a in A:
  ans += x//a
  #ans %= mod
print(ans%mod)

Submission status: Accepted

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

import fractions
from functools import reduce

def gcd(x,y):
  if x == 0:
    return y
  else:
    return gcd(y-x*(y//x),x)
 

def lcm(x, y):
    return (x*y)//gcd(x,y)
    
l = 1
B = 0

for i in range(N):
  l = lcm(l,A[i])
for i in range(N):
  B += l//A[i]
B %= mod

print(B)

Submission status: Accepted

Solution code:
# import math
# import fractions

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

mod = 10 ** 9 + 7


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


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

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

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

Submission status: Accepted

Solution code:
def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y

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

LCM = A[0]
for i in range(0,N-1,1):
    LCM = lcm(LCM,A[i+1])
B = [0 for i in range(0,N,1)]
for i in range(0,N,1):
    B[i]= (LCM%MOD)*pow(A[i],MOD-2,MOD)%MOD

ans = 0
for i in range(0,N,1):
    ans = (B[i] + ans)%MOD

print(ans)