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 collections import defaultdict
facts = defaultdict(int)
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
n=int(input())
a=[int(i) for i in input().split()]
for i in range(n):
  for b,p in factorization(a[i]):
    if facts[b]<p:
      facts[b]=p
ans=0
f=1
for k,v in facts.items():
  f*=pow(k,v,mod)
  f%=mod
for i in range(n):
  ans+=f*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
#最小公倍数を割った商の和を求める
import fractions
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//a[i]
print(ans%mod)

Submission status: Accepted

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


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

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

print(sum([lcm // a for a in A]) % mod)

Submission status: Accepted

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


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

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

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

print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict

def prime_factors(n):
    d = defaultdict(int)
    while n%2 == 0:
        d[2] += 1
        n //= 2
    i = 3
    while i*i <= n:
        while n%i == 0:
            d[i] += 1
            n //= i
        i += 2
    if n > 2:
        d[n] += 1
    return d

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
G = defaultdict(int)
for a in A:
    pf = prime_factors(a)
    for k,v in pf.items():
        G[k] = max(G[k], v)
lcm = 1
for k,v in G.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def prime_factors(n):
    d = {}
    while n%2 == 0:
        d[2] = d.get(2, 0) + 1
        n //= 2
    i = 3
    while i*i <= n:
        while n%i == 0:
            d[i] = d.get(i, 0) + 1
            n //= i
        i += 2
    if n > 2:
        d[n] = d.get(n, 0) + 1
    return d

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))
G = {}
for a in A:
    pf = prime_factors(a)
    for k,v in pf.items():
        G[k] = max(G.get(k, 0), v)
lcm = 1
for k,v in G.items():
    lcm *= pow(k, v, MOD)
    lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD) % MOD
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

primes=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,1009,10**7]
n=int(input())
a=list(map(int,input().split()))
mod = 10**9+7

factors=defaultdict(lambda: 0)

for i in a:
    lfactors=defaultdict(lambda: 0)
    for prime in primes:
        if prime>i:
            lfactors[i]+=1
            break
        while i%prime==0:
            i=i//prime
            lfactors[prime]+=1
    for key,value in zip(lfactors.keys(),lfactors.values()):
        factors[key]=max(factors[key],value)
ans=1
for fact,p in zip(factors.keys(),factors.values()):
    ans=(ans*pow(fact,p))%mod
print(sum([(ans*pow(i,mod-2,mod))%mod for i in a])%mod)

Submission status: Accepted

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

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

N = int(input())
A = list(map(int,input().split()))
l = 1
ans, mod = 0, 1000000007

for x in A:
    l = lcm(l, x)

for x in A:
    ans = ans + l//x
print(ans % mod)

Submission status: Accepted

Solution code:
def get_sieve_of_eratosthenes_new(n):
    import math
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def ord(N,n):#N,nは正の整数、Nで割り切れる回数、許容はN^1000
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

prime=get_sieve_of_eratosthenes_new(1000)

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

data=[[0 for i in range(0,len(prime))] for i in range(0,N)]
nokori=[1 for i in range(0,N)]
largeprime=set([])

import copy
sample=copy.copy(A)
for i in range(0,N):
    for j in range(0,len(prime)):
        a=ord(prime[j],A[i])
        data[i][j]=a
        A[i]=A[i]//(prime[j]**a)

    if A[i]!=1:
        largeprime.add(A[i])
    nokori[i]=A[i]

lcm=[max(data[i][j] for i in range(0,N)) for j in range(0,len(prime))]
largeprime=list(largeprime)

LCM=1
for i in range(0,len(lcm)):
    LCM=(LCM*pow(prime[i],lcm[i],mod))%mod

for i in range(0,len(largeprime)):
    LCM=(LCM*largeprime[i])%mod

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

print(ans)

Submission status: Accepted

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

def eucrid(a,b):
  a,b=max(a,b),min(a,b)
  while True:
    if a%b==0:
      return b
    else:
      a,b=b,a%b
m=a[0]
for i in range(n):
  m=m//eucrid(m,a[i])*a[i]
b=0
m=m%mod
for i in a:
  b+=m*pow(i,mod-2,mod)%mod
print(b%mod)

Submission status: Accepted

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

# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor

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

import sys
input = sys.stdin.readline


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

dic = {}
for a in A:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

lcm = 1
for num, count in dic.items():
    lcm *= pow(num, count, mod)
    lcm %= mod

ans = 0
for a in A:
    ans += mod_inv(a)*lcm
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import collections
import math
n = int(input())
ai = [int(i) for i in input().split()]

mod = 10**9+7

if n == 1:
    print(1)
    exit()
    
    
# 素因数分解、辞書で返すやつ
# mathをimportする
def prime(n):
    factor = {}
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            if not num in factor.keys():
                factor[num] = 1
            else:
                factor[num] += 1
        if num > n:
            break
    if n != 1:
        if not n in factor.keys():
            factor[n] = 1
        else:
            factor[n] += 1
    return factor


dic = {}
for a in ai:
    pr = prime(a)
    for num, count in pr.items():
        if not num in dic.keys():
            dic[num] = count
        else:
            if dic[num] < count:
                dic[num] = count

kari = 1
for num,count in dic.items():
    kari *= pow(num,count,mod)
    kari %= mod

kari_old = kari
ans = 0

for i in range(n):
    kari = kari_old
    #com_ab_new = copy.deepcopy(com_ab)
    #print(com_ab,com_ab_new)
    #kari = 1
    #for j in range(kosu):
    #kari *= pow(sosu_li[j][0],com_ab[sosu_li[j][0]],mod)
    kari *= pow(ai[i],mod-2,mod)
    ans += kari
    ans %= mod
    #print(ans)
    #print(ans)
        
print(ans)

Submission status: Accepted

Solution code:
def prime_factorize(n):
    ans = []
    for i in range(2, int(n ** (1 / 2)) + 1):
        c = 0
        while True:
            if not n % i == 0:
                ans.append([i, c])
                break
            n //= i
            c += 1
        if n == 1:
            break
    if n != 1:
        ans.append([int(n), 1])
    return ans

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
s = [0] * (5 * (10 ** 5))
for i in a:
    p = prime_factorize(i)
    for q in p:
        r = (q[0] - 1) // 2
        s[r] = max(s[r], q[1])
l = 1
for i in range(len(s)):
    l *= pow(max(2 * i + 1, 2), s[i], mod)
    l %= mod
ans = 0
for i in a:
    ans += pow(i, mod - 2, mod) * l % mod
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

from functools import reduce


n = int(input())
a_list = [int(x) for x in input().split()]

temp = 1
for a in a_list:
    temp *= a // gcd(a, temp)

ans = 0
for a in a_list:
    ans += temp // a
mod = 10 ** 9 + 7
ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

from functools import reduce


n = int(input())
a_list = [int(x) for x in input().split()]

temp = 1
for a in a_list:
    temp *= a // gcd(a, temp)

mod = 10 ** 9 + 7
ans = sum([temp // a for a in a_list]) % mod
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

from functools import reduce


n = int(input())
a_list = [int(x) for x in input().split()]

temp = reduce(lambda x, y: (x * y) // gcd(x, y), a_list)

mod = 10 ** 9 + 7
ans = sum([temp // a for a in a_list]) % mod
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    c = 0
    while num%2==0:
        c += 1
        num //= 2
    memo[2] = max(memo[2], c)
    for j in range(3, int(i**.5)+1, 2):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

mod = 10**9 + 7
memo = defaultdict(int)
base = 0
for i in a:
    base = (base+pow(i, mod-2, mod))%mod
    num = i
    for j in range(2, int(i**.5)+1):
        if num%j==0:
            c = 0
            while num%j==0:
                num //= j
                c += 1
            memo[j] = max(memo[j], c)
    if num != 1:
        memo[num] = max(memo[num], 1)
k = 1
for s, t in memo.items():
    k = (k*pow(s, t, mod))%mod

print((k*base)%mod)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
mod = 10**9+7
res = [0]*(max(a)+1)
ma = 0
for i in a:
    for j in range(2,int(i**0.5)+1):
        cnt = 0
        while i%j==0:
            i//=j
            cnt+=1
        res[j] = max(res[j],cnt)
    if i!=1:
        res[i] = max(res[i],1)

d = 1
for i in range(max(a)+1):
    if res[i]>0:
        d=d*i**res[i]%mod
ans = 0
for i in range(n):
    m = pow(a[i],mod-2,mod)
    ans = (ans+(d*m)%mod)%mod
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

def main():
    n = int(input())
    a = list(map(int, input().split()))
    c = lcm(a)
    b = [c // ai for ai in a]
    print(sum(b) % (10 ** 9 + 7))

def lcm(li):
    res = 1
    for x in li:
        res *= (x // gcd(res, x))
    return res

def gcd(x, y):
    if x < y:
        x, y = y, x  # x >= y
    while y > 0:
        r = x % y
        x = y
        y = r
    return x
if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    
    d = defaultdict(int)
    
    for x in a:
        num = x
        count = 0
        while num%2 == 0:
            num //= 2
            count += 1
        d[2] = max(d[2],count)
        for i in range(3,int(x**(1/2))+1,2):
            if num%i == 0:
                count = 0
                while num%i == 0:
                    num //= i
                    count += 1
                d[i] = max(d[i],count)
        if num != 1:
            d[num] = max(d[num],1)

    base = 1
    for x,y in d.items():
        base *= pow(x,y,MOD)
        base %= MOD
        
    s = 0
    for num in a:
        inv_a = pow(num,MOD-2,MOD)
        s += inv_a
        s %= MOD
        
    print((base*s)%MOD)

if __name__ == "__main__":
    main()

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
lcm_val=a[0]
for i in range(n-1):
  lcm_val=lcm(lcm_val,a[i+1])
# print(lcm_val)
b=[]
ans=0
for aa in a:
  ans+=lcm_val//aa

print(ans%mod)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

def many_lcm(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = tmp * l[i]//gcd(tmp, l[i])
    return tmp

lm = many_lcm(A)
ans = 0
for a in A:
    ans += lm // a
print(ans % mod)

Submission status: Accepted

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

def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

bucket = [0] * (M + 1)
for val in A:
    for i in range(2, math.floor(math.sqrt(val)) + 1):
        #print(val, i)
        temp = 0
        while val % i == 0:
            val //= i
            temp += 1
        bucket[i] = max(bucket[i], temp)
    if val != 1:
        bucket[val] = max(bucket[val], 1)
#print(bucket)

L = 1
for n in range(M + 1):
    L = (L * n ** bucket[n]) % MOD
#print(L)

ans = 0
for val in A:
    ans = (ans + power_func(val, MOD - 2, MOD))
ans = (ans * L) % MOD
print(ans)

Submission status: Accepted

Solution code:
def lcm(a, b):
    from fractions import gcd

    return a // gcd(a, b) * b


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    x = 1

    for e in a:
        x = lcm(x, e)

    ans = 0
    for e in a:
        ans += x // e

    print(ans % int(1e9 + 7))


main()

Submission status: Accepted

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

def prime_factorize(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

primes = defaultdict(int)
for a in A:
    for x, p in prime_factorize(a):
        primes[x] = max(primes[x], p)
lcm = 1
for prime, ind in primes.items():
    lcm *= prime ** ind
ans = 0
for i in range(N):
    ans += lcm // A[i]
    if i == N // 2:
        ans %= mod
print(ans % mod)

Submission status: Accepted

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

def gcd(n, m):
    if m == 0:
        return n
    while m != 0:
        n, m = m, n % m
    return n

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

L = 1
for a in A:
    L = lcm(L, a)

ans = 0
for i, a in enumerate(A):
    ans += L // a
    if i == N // 2:
        ans %= MOD

print(ans % MOD)

Submission status: Accepted

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

def gcd(n, m):
    if m == 0:
        return n
    while m != 0:
        n, m = m, n % m
    return n

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

L = 1
for a in A:
    L = lcm(L, a)

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

print(ans % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    import sys
    input = sys.stdin.buffer.readline
    _ = int(input())
    A = [int(i) for i in input().split()]

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

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

    n = 1
    for a in A:
        n = lcm(n, a)
    n %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gcd(n, m):
    if m == 0:
        return n
    while m != 0:
        n, m = m, n % m
    return n

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

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

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

print(ans % MOD)

Submission status: Accepted

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

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

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

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

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

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)
n=int(input())
a=list(map(int,input().split()))
ans=0
mod=10**9+7
l=a[0]
for i in range(1,n):l=lcm(l,a[i])
l%=mod
for i in a:
  ans+=l*pow(i,mod-2,mod)%mod
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int, input().split())
M=10**3

P=[]
isp=[True]*M
for n in range(2,M):
    if isp[n]==False: continue
    P.append(n)
    for m in range(n*n, M, n):
        isp[m]=False

from collections import defaultdict
D=[defaultdict(int) for _ in range(N)]
for i in range(N):
    a=A[i]
    for p in P:
        while a>1:
            if a%p==0:
                D[i][p]+=1
                a//=p
            else:
                break
        else:
            break
    if a>1:
        D[i][a]+=1

d=defaultdict(int)
for i in range(N):
    for k,v in D[i].items():
        d[k] = max(d[k], v)

MOD = 10**9+7
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

gcd=Mint(1)
for k,v in d.items():
    gcd *= pow(k,v,MOD)

print(sum([gcd//a for a in A]))

Submission status: Accepted

Solution code:
N=int(input())
*A,=map(int, input().split())
M=10**3

P=[]
isp=[True]*M
for n in range(2,M):
    if isp[n]==False: continue
    P.append(n)
    for m in range(n*n, M, n):
        isp[m]=False

from collections import defaultdict
D=[defaultdict(int) for _ in range(N)]
for i in range(N):
    a=A[i]
    for p in P:
        while a>1:
            if a%p==0:
                D[i][p]+=1
                a//=p
            else:
                break
        else:
            break
    if a>1:
        D[i][a]+=1

d=defaultdict(int)
for i in range(N):
    for k,v in D[i].items():
        d[k] = max(d[k], v)
gcd=1
for k,v in d.items():
    gcd*=k**v

print(sum([gcd//a for a in A])%(10**9+7))

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]

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

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

    num = 1
    for a in A:
        num = lcm(num, a)
    n = modint(num)

    ans = 0
    for i, a in enumerate(A):
        ans += n/a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

def main():

    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)

    total = 0
    for a in A:
        total += LCM // a
        

    print(total % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

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

import fractions
#import math
from functools import reduce
def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)
  #return (x * y) // math.gcd(x, y)

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

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

Submission status: Accepted

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

def lcm(a, b):
    a, b = max(a, b), min(a, b)
    c = a * b
    while a % b > 0:
        a, b = b, a % b
    return c // b

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    L = A[0]
    for i in range(1, N): L = lcm(L, A[i])
    L %= mod
    ans = 0
    for a in A:
        ans += (L * pow(a, mod - 2, mod)) % mod
        ans %= mod
    print(ans)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

L = 1
for a in A:
    L = lcm(L, a)

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

Submission status: Accepted

Solution code:
import sys

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


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

    def factorization(n):
        factors = []

        while n % 2 == 0:
            factors.append(2)
            n //= 2

        for i in range(3, int(n ** 0.5) + 5, 2):
            while n % i == 0:
                factors.append(i)
                n //= i
        if n != 1:
            factors.append(n)

        return Counter(factors)

    a_fac = [0] * n

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

    lcm = {1: 1}

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

    ans = 0

    lcmmod = 1

    for key, value in lcm.items():
        lcmmod *= pow(key, value, MOD)
        lcmmod %= MOD

    for ele in a:
        ainv = pow(ele, MOD - 2, MOD)
        ans += ((lcmmod*ainv) % MOD)
        ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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