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: Time Limit Exceeded

Solution code:
MOD=10**9+7
import fractions
N=int(input())
if N==1:
  A=int(input())
  print(1)
  exit()
  
A=list(map(int, input().split()))

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

tmp=f(A[0], A[1])
for i in range(2, N):
  tmp=f(tmp, A[i])
  
out=0
for i in range(N):
  out+=tmp//A[i]
  out%=MOD

print(out)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def main():
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    l = A[0]
    for i in A[1:]:
        g = fractions.gcd(g, i)
        l = l * i // fractions.gcd(l, i)
    r = 0
    mod = 10 ** 9 + 7
    n = l // g
    for i in A:
        r += (n // (i // g)) % mod
    print(r % mod)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from bisect import bisect, bisect_left

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

def solve():
    input = sys.stdin.readline
    mod = 7 + 10 ** 9
    N = int(input())
    A = [int(a) for a in input().split()]
    if N == 1: print(1)
    else:
        lcm = A[0]
        for i in range(1, N):
            gcd_a = gcd(lcm, A[i])
            lcm = lcm * A[i] // gcd_a
        sumB = 0
        for i in range(N):
            sumB += lcm // A[i]
            sumB %= mod

        print(sumB)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from fractions import gcd
    input = sys.stdin.readline

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

    X = A[0]
    for i in range(1, N):
        g = gcd(X, A[i])
        X = (X * A[i]) // g
    ans = 0
    for i in range(N):
        ans = (ans + X // A[i])%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

mod = 10**9 + 7

N = int(input())
A = [int(i) for i in input().split()]
num = 1
for n in A:
    num = (num*n)//gcd(num,n)
t = 0
for n in A:
    t = (t + num//n) % mod
print(t)

Submission status: Time Limit Exceeded

Solution code:
from fractions import Fraction as F
from fractions import gcd

MOD = 10 ** 9 + 7

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

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

# B_1 = 1と仮定
b = [F(1, 1)]
for i in range(1, n):
    b.append(F(a[0], a[i]))

al_lcm = 1
for i in b:
    al_lcm = lcm(al_lcm, i.denominator)

# print(al_lcm)

res = 0
for i in b:
    res += i * al_lcm

print(res % MOD)

# print(b)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

def lcm_list(numbers):
    return reduce(lcm, numbers)

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

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

Submission status: Time Limit Exceeded

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

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

def lcm_list(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = lcm_base(tmp, l[i])
    return tmp

lcm = lcm_list(a)
mod = 10**9+7


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

#a,bの最大公約数
def gcd(a, b):
   while b:
       a, b = b, a % b
   return a

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


tmp = 1
for a in al:
    tmp = lcm(tmp, a)

ans = 0
for a in al:
    ans += tmp // a
    ans %= 10**9 + 7

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
ans = 0
mod = 10 ** 9 + 7
for i in range(n):
  tmp = lcm // a[i]
  tmp %= mod
  ans += tmp
  ans %= mod
print(ans)
#print(lcm)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


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


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


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

res = 0
for i, a in enumerate(A):
    res = (res + l // A[i]) % MOD

print(res)

Submission status: Time Limit Exceeded

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

from fractions import gcd

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

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

ans = 0
for i in range(N):
    ans += AA//A[i]
    
mod = 10**9 + 7
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions 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
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

def primes(n):
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n//3)
    for i in range(1, int(n**0.5)//3+1):
        if sieve[i]:
            k = 3*i+1|1
            sieve[k*k//3::2*k] = [False] * ((n//6-k*k//6-1)//k+1)
            sieve[k*(k-2*(i&1)+4)//3::2*k] = [False] * ((n//6-k*(k-2*(i&1)+4)//6-1)//k+1)
    return [2, 3] + [3*i+1|1 for i in range(1, n//3-correction) if sieve[i]]

N = int(input())
A = [int(x) for x in input().split()]
ps = primes(int(max(A)**0.5)+1)
dic = defaultdict(lambda : 0)
for a in A:
    for i in ps:
        if a < i:
            break
        if a % i == 0:
            c = 0
            while a % i == 0:
                c += 1
                a //= i
            if dic[i] < c:
                dic[i] = c
    if a > 1 and dic[a] == 0:
        dic[a] = 1
MAX = 1
for k in dic:
    MAX *= pow(k, dic[k])
ans = 0
for a in A:
    ans += MAX//a
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

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

#最小公倍数でよいか？
#全てのjについてAiBiはAjで割り切れる
#計算時間は？
from fractions import gcd
mod =10**9+7
def lcd(x,y):
    g = gcd(x,y)
    return x*y//g

ag = 1
for i in range(n):
    ag = lcd(ag,a[i])

ans = 0

for i in range(n):
    ans += ag//a[i]
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
# from math import gcd

mod = 10**9 + 7

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

N = int(input())
A = [int(i) for i in input().split()]
num = 1
for n in A:
    num = lcm(num, n)
t = 0
for n in A:
    t =  (t + num//n) % mod
print(t)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
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]
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
INF = 500000
mod = 10**9+7

N = int(input())
A = [int(x) for x in input().split()]
dic = defaultdict(lambda : 0)
for a in A:
    for i in range(2, int(a**0.5)+1):
        if a % i == 0:
            c = 0
            while a % i == 0:
                c += 1
                a //= i
            if dic[i] < c:
                dic[i] = c
    if a > 1 and dic[a] == 0:
        dic[a] = 1
MAX = 1
for k in dic:
    MAX *= pow(k, dic[k])
ans = 0
for a in A:
    ans += MAX//a
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce

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

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

x = reduce(lcm, a)

ans = 0
for i in range(n):
    ans += x // a[i]

print(ans%1000000007)

Submission status: Accepted

Solution code:
from collections import Counter

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

lcm = Counter([])
for a in A:
    tmp = []
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a != 1:
        tmp.append(a)
    tmp = Counter(tmp)
    for k,v in tmp.items():
        if k not in lcm or v > lcm[k]:
            lcm[k] = v

LCM = 1
for k,v in lcm.items():
    LCM = LCM * pow(k,v,mod) % 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
     
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
     
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
      
N = int(input())
A = list(map(int,input().split()))
ans = 0
     
lcm = lcm_list(A)
     
for i in range(N):
    ans += lcm//A[i]
     
print(ans%1000000007)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

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

    a_lcm = reduce(lcm, a)
    print(sum([a_lcm * pow(aa, mod - 2, mod) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
A = list(map(int,input().split()))
ans = 0

lcm = lcm_list(A)

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

print(ans%1000000007)

Submission status: Accepted

Solution code:
from collections import defaultdict

ps = []
for i in range(2, 1000):
    is_p = True
    for j in range(2, i):
        if i % j == 0:
            is_p = False
            break
    if is_p:
        ps.append(i)

def factorization(n):
    arr = defaultdict(int)
    temp = n
    for i in ps:
        if i > int(-(-n**0.5//1))+1:
            break
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr[i] = cnt
    if temp!=1:
        arr[temp] = 1
    if arr==[]:
        arr[n] = 1
    return arr


aa = defaultdict(int)

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

fs = [[]] * 1000001
for i in a:
    if not fs[i]:
        fs[i] = factorization(i)

for i in a:
    for k, v in fs[i].items():
        aa[k] = max(aa[k], v)


mod = 10 ** 9 + 7
t = 1
for k, v in aa.items():
    t = (t * (k ** v)) % mod
ans = 0
for i in a:
    ans += t * pow(i, mod - 2, mod)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

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

def gcd(l):
    ans = 0
    for i in l:  ans = gcd_(ans, i)
    return ans

def lcm_(x,y):
    return (x * y) // gcd_(x, y)

def lcm(l):
    ans = l[0]
    for i in l:  ans = lcm_(ans, i)
    return ans

N = cin()[0]
v = cin()
lc = lcm(v)
ans = 0
INF = 10 ** 9 + 7
lc %= INF
for i in range(N):
    ans += lc * pow(v[i], INF - 2, INF)
    ans %= INF
print(int(ans))

Submission status: Accepted

Solution code:
import math
N = int(input())
A = list(map(int,input().split()))
B = [0] * (N)
lcmall = A[0]
for i in range(1,N):
    gcdall = math.gcd(lcmall,A[i])
    lcmall = lcmall*A[i] // gcdall
sum = 0
for i in range(N):
    B[i] =int(lcmall // A[i])
    sum += B[i]
print(sum % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
from collections import Counter

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

divide = []
for a in A:
    tmp = []
    d = 2
    while d*d <= a:
        while a % d == 0:
            a //= d
            tmp.append(d)
        d += 1
    if a != 1:
        tmp.append(a)
    divide.append(Counter(tmp))

count = Counter([])
for d in divide:
    for k,v in d.items():
        if k not in count:
            count[k] = v
        else:
            count[k] = max(count[k],v)

LCM = 1
for k,v in count.items():
    LCM *= pow(k,v,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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from collections import defaultdict
    #nの素因数分解，[[a1,b1],[a2,b2]...]   aがb個,
    def factorization(n):
        if n==1:
            return [[1,0]]
        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
    
    lcm_dd = defaultdict(int)
    
    N=I()
    A=LI()
    for i in range(N):
        a=A[i]
        arr=factorization(a)
        for v in arr:
            p,cnt=v
            lcm_dd[p]=max(lcm_dd[p],cnt)
            
    lcm=1
    for k,v in lcm_dd.items():
        temp=pow(k,v,mod)
        lcm=(lcm*temp)%mod
        
    ans=0
    for i in range(N):
        temp=(lcm*pow(A[i],mod-2,mod))%mod
        ans=(ans+temp)%mod
        
    print(ans%mod)
        
    


main()

Submission status: Accepted

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

divide = []
for i in range(N):
    a = A[i]
    tmp = []
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a != 1:
        tmp.append(a)
    divide.append(Counter(tmp))

lcm = Counter([])
for count in divide:
    for k,v in count.items():
        if k not in lcm:
            lcm[k] = v
        else:
            lcm[k] = max(lcm[k],v)

mod = 10**9 +7
LCM = 1
for k,v in lcm.items():
    LCM *= pow(k,v,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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


def eratosthenes(n):
    p = []
    t = [-1] * n

    for i in range(2, int(math.ceil(math.sqrt(n)))):
        if t[i] == -1:
            p.append(i)
            t[i] = i
            for j in range(2*i, n, i):
                if t[j] == -1:
                    t[j] = i

    for j in range(i+1, n):
        if t[j] == -1:
            p.append(j)
            t[j] = j

    return p, t

P, T = eratosthenes(10**6+1)

@mt
def slv(N, A):
    c = Counter()
    for a in A:
        while a != 1:
            p = T[a]
            t = 0
            while a % p == 0:
                t += 1
                a //= p
            if t > 0:
                c[p] = max(c[p], t)
            if a == 1:
                break

    M = Mod(10**9+7)
    L = 1
    for k, v in c.items():
        L = M.mul(L, M.pow(k, v))

    ans = 0
    for a in A:
        ans = M.add(ans, M.div(L, a))

    return ans




def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, A):
    M = Mod(10**9 + 7)
    def lcm(a, b):
        return a // math.gcd(a, b) * b
    b = reduce(lcm, A)
    ans = 0
    for a in A:
        ans = M.add(ans, M.div(b, a))
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

mod = 10**9 + 7
# A全体の最小公倍数
a_lcm = 1
for a in A:
    a_lcm = lcm(a_lcm, a)

# Bの総和
b_sum = 0
for i in range(N):
    b_sum += a_lcm // A[i]

print(b_sum % mod)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+1)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+5)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6+2):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Submission status: Accepted

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


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


prime = [0] * (10**6+1)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1], prime[j[0]])
lcm = 1
for i in range(10**6):
    if prime[i] > 0:
        lcm *= pow(i, prime[i],MOD)

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

Submission status: Accepted

Solution code:
import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations, zip_longest, groupby


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

modulo = 10**9+7


def merge(A, start, end, divisors):
    if start == end:
        return Counter(divisors[A[start]])
    mid = start+(end-start)//2
    left = merge(A, start, mid, divisors)
    right = merge(A, mid+1, end, divisors)
    for r in right:
        left[r] = max(left[r], right[r])
    return left

def solve() -> int:
    N = read_int()
    A = read_ints()
    M = 10**6+1
    divisors: List[List[int]] = [[] for _ in range(M)]
    for i in range(2, M):
        if len(divisors[i]) == 0:
            for j in range(i, M, i):
                temp = j
                while temp%i == 0:
                    divisors[j].append(i)
                    temp //= i
    lcd_counter = merge(A, 0, N-1, divisors)
    lcd = 1
    for k in lcd_counter:
        lcd = (lcd*pow(k, lcd_counter[k], modulo))%modulo
    answer = 0
    for a in A:
        answer = (answer+(lcd*pow(a, modulo-2, modulo))%modulo)%modulo
    return answer


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

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

a_lcm = 1
for ai in a:
    a_lcm = lcm(a_lcm, ai)

b_sum = 0
for i in range(n):
    b_sum += a_lcm // a[i]

print(b_sum%mod)

Submission status: Accepted

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

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

a_lcm = 1
for ai in a:
    a_lcm = lcm(a_lcm, ai)

b_sum = 0
for ai in a:
    b_sum += a_lcm // ai

print(b_sum%mod)

Submission status: Accepted

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

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

a_lcm = 1
for i in range(n):
    a_lcm = lcm(a_lcm, a[i])

b_sum = 0
for ai in a:
    b_sum += a_lcm // ai

print(b_sum%mod)

Submission status: Accepted

Solution code:
from collections import Counter
MOD = 10**9+7
N = int(input())
A = list(map(int,input().split()))
def prime_factorize(n):
    N = n
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= N:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
prime = [0] * (10**6+5)
for i in range(N):
    c = Counter(prime_factorize(A[i]))
    for j in c.items():
        prime[j[0]] = max(j[1],prime[j[0]])
lcm = 1
for i in range(10**6+2):
    if prime[i] > 0:
        lcm *= pow(i,prime[i])
        lcm %= MOD

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

Submission status: Accepted

Solution code:
from functools import reduce

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

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

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

LCM = reduce(lcm,A)%mod

print(sum([LCM*pow(A[i],-1,mod)%mod for i in range(N)])%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

print(ans)

Submission status: Accepted

Solution code:
from copy import copy
def prime_table(n):
  n+=1
  table=[i if i%2 else 2 for i in range(n)]
  for i in range(3,n,2):
    if table[i]==i:
      for j in range(i*i,n,2*i):
        if table[j]==j:
          table[j]=i
  return table


def prime_fact(n,table):
  p=[]
  while n!=1:
    pp=table[n]
    p.append(pp)
    n//=pp
  r={}
  for i in p:
    if i in r:
      r[i]+=1
    else:
      r[i]=1
  return r



n=int(input())
t=prime_table(10**6)
a=list(map(lambda x:prime_fact(int(x),t),input().split()))

mx=copy(a[0])
for i in a[1:]:
  for j in i:
    if j in mx:
      mx[j]=max(mx[j],i[j])
    else:
      mx[j]=i[j]


sm=0
mod=10**9+7
for i in a:
  r=1
  for j in i:
    r=(r*pow(j,i[j],mod))%mod
  sm=(sm+pow(r,mod-2,mod))%mod

  
p=1
for i in mx:
  p=(p*pow(i,mx[i],mod))%mod

print((sm*p)%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import math
n = int(input()) 
a = list(map(int, input().split()))

mod = 10**9+7

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

l = a[0]
for i in range(n):
    l = lcm(l, a[i])
l %= mod 

ans = 0 
for i in range(n):
    inv = pow(a[i], mod-2, mod)
    ans += (l*inv)%mod

print(ans%mod)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
memo = []
for i in range(N):
    tmp = []
    a = A[i]
    d = 2
    while d*d <= a:
        while a%d == 0:
            tmp.append(d)
            a //= d
        d += 1
    if a!=1:
        tmp.append(a)
    memo.append(Counter(tmp))

lcm = Counter([])

for count in memo:
    for k,v in count.items():
        if k not in lcm:
            lcm[k] = v
        else:
            lcm[k] = max(lcm[k],v)
mod = 10**9 +7
LCM = 1
for k,v in lcm.items():
    LCM = LCM*pow(k,v)%mod

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

Submission status: Accepted

Solution code:
import math
n = int(input())
a = list(map(int, input().split()))
s = a[0]
for i in a[1:]:
    s = (s*i)//math.gcd(s,i)
num = 0
for h in a:
    num += (s//h)
print(num%((10**9)+7))

Submission status: Accepted

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
from math import gcd
def lcm(a,b):
    return a*b//gcd(a,b)
def main():
    mod = 10**9 +7
    N = int(input())
    A = list(map(int,input().split()))
    l = A[0]
    for i in range(1,N):
        l = lcm(l,A[i])

    ans = 0
    for a in A:
        ans += l//a
    print(ans%mod)
main()

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