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:
import sys
from collections import Counter
from functools import reduce
from operator import mul, ior

from typing import Callable, ClassVar, Sequence, Type, TypeVar


T = TypeVar('T', bound='ModIntBase')


class ModIntBase:
    value: int
    mod: ClassVar[int]
    fac: ClassVar[Sequence[int]] = ()
    inv: ClassVar[Sequence[int]] = ()
    finv: ClassVar[Sequence[int]] = ()

    def __init__(self, value: int) -> None:
        self.value = value % self.mod

    def __hash__(self) -> int:
        return hash((self.value, self.mod))

    def __eq__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value == other.value
        else:
            return NotImplemented

    def __ne__(self, other) -> bool:
        if isinstance(other, self.__class__):
            return self.value != other.value
        else:
            return NotImplemented

    # TODO: Add type hints
    def __add__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value + other.value) % self.mod)
        else:
            return NotImplemented

    def __sub__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__((self.value - other.value) % self.mod)
        else:
            return NotImplemented

    def __mul__(self, other):
        if isinstance(other, self.__class__):
            return self.__class__(self.value * other.value % self.mod)
        else:
            return NotImplemented

    def __truediv__(self, other):
        if isinstance(other, self.__class__):
            a = other.value
            b = self.mod
            u = 1
            v = 0
            while b:
                t = a // b
                a, b = b, a - t * b
                u, v = v, u - t * v
            return self.__class__(self.value * u % self.mod)
        else:
            return NotImplemented

    def __pow__(self, other):
        if isinstance(other, self.__class__):
            v = 1
            a = self.value
            b = other.value
            mod = self.mod
            while b > 0:
                if b & 1:
                    v = v * a % mod
                a = a * a % mod
                b >>= 1
            return self.__class__(v)
        else:
            return NotImplemented

    @classmethod
    def comb(cls, n: int, k: int):
        if n < k:
            return cls(0)
        if n < 0 or k < 0:
            return cls(0)

        if n < len(cls.fac):
            return cls(cls.fac[n] * (cls.finv[k] * cls.finv[n - k] % cls.mod) % cls.mod)
        else:
            k = min(k, n - k)
            a = reduce(mul, map(cls, range(n - k + 1, n + 1)), cls(1))
            b = reduce(mul, map(cls, range(1, k + 1)), cls(1))
            return a / b

    def __repr__(self) -> str:
        return f'{self.__class__.__name__}({self.value!r})'

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


class ModInt(ModIntBase):
    mod = 1000000007  # 10 ** 9 + 7


def prime_factor(a, temp):
    while a > 1:
        yield temp[a]
        a //= temp[a]


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    max_a = max(A)
    temp = [0] * (max_a + 1)
    temp[1] = 1

    for i in range(2, max_a + 1):
        if temp[i]:
            continue

        for j in range(i, max_a + 1, i):
            temp[j] = i
    
    ap_list = (Counter(prime_factor(a, temp)) for a in A)
    lcm = reduce(ior, ap_list, Counter())
    lcm_i = ModInt(1)
    for v in lcm.elements():
        lcm_i *= ModInt(v)


    ans = ModInt(0)
    for a in A:
        ans += lcm_i / ModInt(a)

    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gcd(p,q):
    if q == 0:
        return p
    else:
        return gcd(q,min(p%q,q-p%q))

if N != 1:
    lcm = 1
    for i in range(N-1):
        if i == 0:
            lcm = A[0]*A[1]//gcd(A[0],A[1])
        else:
            lcm = lcm*A[i+1]//gcd(lcm,A[i+1])

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

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

else:
    print(1)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        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=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

lcm = 1
for key,val in d.items():
    lcm = lcm*pow(key,val)

ans = 0
for a in A:
    ans = ans+lcm//a
print(ans%m)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

def factorization(n):
    arr = []
    temp = n
    i=2
    if temp%i==0:
        cnt=0
        while temp%i==0:
            cnt+=1
            temp //= i
        arr.append([i, cnt])
            
    for i in range(3, int(-(-n**0.5//1))+1,2):
        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=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = ans+gcd//a
print(ans%m)

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


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


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def solve():
    n = getN()
    nums = getList()
    d = dict()
    for num in nums:
        res = primeFactor(num)
        for k, v in res.items():
            if k not in d:
                d[k] = v
            elif d[k] < v:
                d[k] = v


    big = 1
    for k, v in d.items():
        big *= pow(k, v, MOD)
        big %= MOD
    ans = 0
    for num in nums:
        ans += big * divide(num)
        ans %= MOD

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
from math import gcd
def inv(n, p):
    """
    mod p の逆元
    """
    return pow(n, p-2, p)
def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += inv(a, mod)
    ans *= LCM % mod

    print(ans % mod)
main()

Submission status: Accepted

Solution code:
from math import gcd

def mod_prod(X,M):
    c=1
    for x in X:
        c*=x
        c%=M
    return c

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

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

P=mod_prod(E,Mod)

Q=0
for a in A:
    Q+=pow(a,Mod-2,Mod)
    Q%=Mod
print((P*Q)%Mod)

Submission status: Accepted

Solution code:
import math

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

mod = 10**9+7

primes = [0]*(10**6+1)

def prime_fac(n):
  temp = n
  Flag = True
  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      primes[i] = max(primes[i], cnt)
      Flag = False
  if temp != 1:
    primes[temp] = max(primes[temp], 1)
  if Flag:
    primes[n] = max(primes[n], 1)

for a in A:
  prime_fac(a)

LCM = 1
for p, i in enumerate(primes):
  if i:
    LCM *= pow(p, i, 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:
import math

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

mod = 10**9+7

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

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

#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:
import math

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

mod = 10**9+7

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

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

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:
import math
from functools import reduce


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

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


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


lcm_a = lcm(A) % P
ans = 0
for a in A:
    a_inv = pow(a, P-2, P)
    ans = (ans + lcm_a*a_inv) %P
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
dd = defaultdict(int)
ans = 0
for a in alst:
    ans += pow(a, MOD - 2, MOD)
    ans %= MOD
    num = a
    for i in range(2, int(a ** 0.5) + 1):
        cnt = 0
        while num % i == 0:
            num //= i
            cnt += 1
        if cnt > 0:
            dd[i] = max(dd[i], cnt)
    if num != 1:
        dd[num] = max(dd[num], 1)
for key, value in dd.items():
    ans *= pow(key, value, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split( )))
mod = 10**9 + 7
#Aたちの最小公倍数をMとすれば
#答えはsum_{i}M/A_{i} (mod 10**9 + 7)
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

#(A,B,C)の最小公倍数　=(A,B)の最小公倍数とCの最小公倍数を利用すれば簡単そう.
a = 1
c = 0
s = 0
for i in range(n):
  q = lcm(a,A[i])
  s*=q//a
  a = q
  s+=q//A[i]
print(s%mod)

Submission status: Accepted

Solution code:
### 素因数分解する。
from collections import defaultdict

def factorize(n):
    """

    """
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i==0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in LCM:
                LCM[i] = max(LCM[i], cnt)
            else:
                LCM[i] = cnt
    if tmp != 1:
        if tmp in LCM:
            LCM[tmp] = max(LCM[tmp], 1)
        else:
            LCM[tmp] = 1
    if not LCM:
        if n in LCM:
            LCM[n] = max(LCM[n], 1)
        else:
            LCM[n] = 1
def inv(n, p):
    return pow(n, p-2, p)

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

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

lcm = 1
for key, val in LCM.items():
    lcm *= pow(key, val, mod)
    lcm %= mod

inv_sum = 0
for i in range(N):
    inv_sum += inv(A[i], mod)
    inv_sum %= mod

print(lcm * inv_sum % mod)

Submission status: Accepted

Solution code:
from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()

Submission status: Accepted

Solution code:
def factorize(n):
    tmp = n

    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in fact:
                fact[i] = max(fact[i],cnt)
            else:
                fact[i] = cnt
         
    if tmp != 1:
        if tmp in fact:
            fact[tmp] = max(fact[tmp],1)
        else:
            fact[tmp] = 1
    
    if len(fact) == 0:
        if N in fact:
            fact[N] = max(fact[N],1)
        else:
            fact[N] = 1

def inv(n, p):
    return pow(n, p-2, p)
    
N = int(input())
A = list(map(int, input().split()))
p = 10**9+7

fact = {}

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

lcm = 1

for key, val in fact.items():
    lcm *= pow(key, val, p)
    lcm %= p

inv_sum = 0

for i in range(N):
    inv_sum += inv(A[i], p)
    inv_sum %= p

print(lcm * inv_sum % p)

Submission status: Accepted

Solution code:
n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import defaultdict
from math import sqrt, ceil
def factors(x):
    d = defaultdict(int)
    while x % 2 == 0:
        d[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            d[i] += 1
            x //= i
    if x > 1:
        d[x] += 1
    return d

factors_of_aa = list(map(factors, aa))

factors_of_lcm = defaultdict(int)
for factors_of_a in factors_of_aa:
    for k in factors_of_a:
        factors_of_lcm[k] = max(factors_of_lcm[k], factors_of_a[k])
lcm = 1
for factor, cnt in factors_of_lcm.items():
    lcm *= pow(factor, cnt, MOD)

ans = 0
for factors_of_a in factors_of_aa:
    to_add = lcm
    for factor, cnt in factors_of_a.items():
        to_add *= pow(factor, -cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

print(ans)

Submission status: Accepted

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

mod=1000000007
n=input();
arr = list(map(int, raw_input().split()))
l=arr[0];
for i in arr:
    x=gcd(l,i)
    l=(l*i)/x
    
ans=0
#print l
for i in arr:
    b=l/i
    ans+=b
ans=(ans%mod +mod)%mod
print ans

Submission status: Accepted

Solution code:
from math import gcd
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=a[0]
for i in a[1:]:
  c=c*i//gcd(c,i)
ans=0
c%=mod
for i in a:
  ans+=c*pow(i,mod-2,mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

# https://atcoder.jp/contests/abc152/submissions/15835670


def fast_prime_factorization_many(lst):
    # 素因数分解（ロー法、複数）
    from subprocess import Popen, PIPE
    res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
    return [Counter(list(map(int, r.split()[1:]))) for r in res]


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    if N == 1:
        print(1)
        exit(0)

    mod = int(1e9+7)
    Factors = fast_prime_factorization_many(A)
    # print(Factors)
    # lcmを求める
    lcm = 1
    max_factor = [0] * (1000010)
    for f in Factors:
        for k, v in f.items():
            v_prev = max_factor[k]
            if v_prev < v:
                for i in range(v-v_prev):
                    lcm = lcm * k % mod
                max_factor[k] = v

    ans = 0
    for a in A:
        wk = lcm * pow(a, mod-2, mod)
        # print(wk)
        ans += wk
        ans %= mod
    print(ans)
    exit(0)


main()

Submission status: Accepted

Solution code:
from itertools import groupby
from collections import Counter

### https://atcoder.jp/contests/abc152/submissions/15835670
def fast_prime_factorization_many(lst):
  # 素因数分解（ロー法、複数）
  from subprocess import Popen, PIPE
  res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
  return [Counter(list(map(int, r.split()[1:]))) for r in res]

def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  if N == 1:
    print(1)
    exit(0)
  
  mod = int(1e9+7)
  Factors = fast_prime_factorization_many(A)
  #print(Factors)
  ### lcmを求める
  lcm = 1
  max_factor = [0] * (1000010)
  for f in Factors:
    for k,v in f.items():
      v_prev = max_factor[k]
      if v_prev < v:
        for i in range(v-v_prev):
          lcm = lcm * k % mod
        max_factor[k] = v
        
  #print(lcm)
  ans = 0
  for a in A:
    wk =  lcm * pow(a,mod-2,mod)
    #print(wk)
    ans += wk
    ans %= mod
  print(ans)
  exit(0)
  
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()



D = defaultdict(int)
for i in range(n):
    a = A[i]
    Di = defaultdict(int)
    for j in range(2, int(a ** 0.5) + 1):
        while a % j == 0:
            a //= j
            Di[j] += 1
    if a:
        Di[a] += 1
    for k in Di:
        D[k] = max(D[k], Di[k])

ret = 1
for ki in D:
    ret = ret * pow(ki, D[ki], mod)
    ret %= mod

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()



D = defaultdict(int)
for i in range(n):
    a = A[i]
    Di = defaultdict(int)
    for j in range(2, int(a ** 0.5) + 1):
        while a % j == 0:
            a //= j
            Di[j] += 1
        if a == 0:
            break
    if a:
        Di[a] += 1
    for k in Di:
        D[k] = max(D[k], Di[k])

ret = 1
for ki in D:
    ret = ret * pow(ki, D[ki], mod)
    ret %= mod

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

print(ans)

Submission status: Accepted

Solution code:
def gcd (a, b):
    while b != 0:
        a, b = b, a%b
    return a
 
def lcm(a, b,mod):
    return a*b//gcd(a,b)
 
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
b = 1
for i in range(N):
    a = A[i]
    b = lcm(a,b,mod)
ans = 0
for a in A:
    ans += b//a
print(ans%mod)

Submission status: Accepted

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

def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x
      
def lcm(x, y, MOD):
  return x * y // gcd(x, y)

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

Submission status: Accepted

Solution code:
def main():
    import copy
    n = int(input())
    a = list(map(int,input().split()))
    A = copy.deepcopy(a)
    mod = 10**9+7
    l = {}
    for i in range(n):
        for j in range(2,int(a[i]**0.5)+1):
            if a[i]%j==0:
                cnt = 0
                while a[i]%j==0:
                    cnt += 1
                    a[i] = a[i]//j
                if l.get(j)==None:
                    l[j] = cnt
                else:
                    l[j] = max(cnt,l[j])
        if a[i]!=1:
            if l.get(a[i])==None:
                l[a[i]] = 1
    L = 1
    for k in l.keys():
        L *= pow(k,l[k],mod)
    L = L%mod
    ans = 0
    for i in range(n):
        ans += L * pow(A[i],mod-2,mod) % mod
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

def lcm(A):
    from fractions import gcd
    x = A[0]
    for a in A:
        x = (x * a) // math.gcd(x, a)
    return x

l = lcm(A)

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

print(ans % mod)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split(' ')))

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
hoge = 1
for p in l:
    hoge = lcm(hoge, p)
ans = 0
for p in l:
    ans += hoge // p
print(ans % int(1e9 + 7))  # TLE ????

Submission status: Accepted

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

mod = 1000000007

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

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

def pow(p, k):
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = mul(ret, b)
        b = mul(b, b)
        k //= 2
    return ret

def inv(p, k):
    return pow(p, mod - k - 1)

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while ai > 1:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p = p + 1 if p * p < ai else ai

lcmv = 1
for p in lcm:
    lcmv = mul(lcmv, pow(p, lcm[p]))

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = mul(prod, inv(p, ps[i][p]))
    ret = add(ret, prod)

print(ret)

Submission status: Accepted

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

lcmv = 1
for p in lcm:
    lcmv = (lcmv * (p ** lcm[p])) % mod

def inv(p, k):
    k = mod - k - 1
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = (ret * b) % mod
        b = (b * b) % mod
        k //= 2
    return ret

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = (prod * inv(p, ps[i][p])) % mod
    ret = (ret + prod) % mod

print(ret)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

mod = 10 ** 9 + 7


def factorization(n):
    """ n の素因数分解

    Args:
        n (int): [description]

    Returns:
        [type]: [description]
    """

    arr = []
    tmp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):  # sqrt(n) まで
        # i で割れるだけ割る、を繰り返す
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            arr.append([i, cnt])  # 結果を追加

    if tmp != 1:
        arr.append([tmp, 1])  # まだ余っていれば追加しておく

    if arr == []:
        arr.append([n, 1])  # このブロック、必要か？

    return arr


def main():

    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    # 最小公倍数を作る
    p = defaultdict(int)  # p に 因数 : 指数 でもたせる
    for a in A:
        for x, y in factorization(a):
            p[x] = max(p[x], y)

    # 一旦、全部の掛け合わせを作る
    U = 1
    for x, y in p.items():
        U = (U * pow(x, y, mod)) % mod

    # 足す
    ans = 0
    for a in A:
        ans = (ans + U * pow(a, mod - 2, mod)) % mod  # 逆元を

    print(ans)


main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import copy

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 素因数分解
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 resolve(test_def_name=""):
    n = int(input())
    a_s = list(map(int, input().split()))

    input_fact_s = []
    need_s = {}
    # 最小公倍数(素因数)割り出し
    for a in a_s:
        aaa = factorization(a)
        input_fact_s.append(aaa)
        for fact in aaa:
            need_s[fact[0]] = max(fact[1], need_s.get(fact[0], 0))
    lcm = 1
    for val, cnt in need_s.items():
        lcm = (lcm * pow(val, cnt))

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

    print(ans % (pow(10, 9) + 7))

    # テストクラス


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
2 3 4"""
        output = """13"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
12 12 12 12 12"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """3
1000000 999999 999998"""
        output = """996989508"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split(' ')))

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
hoge = 1
for p in l:
    hoge = lcm(hoge, p)
ans = 0
for p in l:
    ans += hoge // p
print(ans % int(1e9 + 7))  # TLE ????