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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
A = LIST()

#素因数分解
def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		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
	
p = defaultdict(int)
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)

Submission status: Accepted

Solution code:
from itertools import groupby

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 [list(map(int, r.split()[1:])) for r in res]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9+7
    max_factor = [0] * (1010101)
    lcm = 1
    Factors = fast_prime_factorization_many(A)
    for factors in Factors:
        for prime, group in groupby(factors):
            n = len(list(group))
            n_old = max_factor[prime]
            if n_old < n:
                for i in range(n - n_old):
                    lcm = lcm * prime % mod
                max_factor[prime] = n
    ans = 0
    for a in A:
        ans += pow(a, mod-2, mod)
    ans = ans * lcm % mod
    print(ans)

main()

Submission status: Accepted

Solution code:
import math
 
mod = 1000000007
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
 
n=int(input())
 
a = list(map(int,input().split()))
 
memo = a[0]
 
for i in range(1,n):
    memo = lcm(memo,a[i])
 
ans = 0
 
for i in range(n):
    ans += memo*pow(a[i], mod-2, mod)%mod
    ans %= mod
 
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    A = LI()

    def lcm(a, b): return a * b // math.gcd(a, b)
    l = reduce(lcm, A, 1) % MOD

    ans = 0
    for ai in A:
        ans = (ans + l * pow(ai, MOD - 2, MOD)) % MOD

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    N = I()
    A = LI()

    def lcm(a, b): return a * b // math.gcd(a, b)
    l = reduce(lcm, A, 1)

    ans = 0
    for ai in A:
        ans = (ans + l * pow(ai, MOD - 2, MOD)) % MOD

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

class FactInv:
    def __init__(self, N, MOD=MOD):
        fact, inv = [1]*(N+1), [None]*(N+1)
        for i in range(1, N+1): fact[i] = fact[i - 1] * i % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N)[::-1]: inv[i] = inv[i + 1] * (i + 1) % MOD
        self.N, self.MOD, self.fact, self.inv = N, MOD, fact, inv

    def perm(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD

class Eratosthenes:
    # https://cp-algorithms.com/algebra/prime-sieve-linear.html
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N = I()
    A = LI()

    era = Eratosthenes(max(A))
    factors = Counter()

    for ai in A:
        cai = Counter(era.factors(ai))
        for k in cai.keys():
            factors[k] = max(factors[k], cai[k])

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

    ans = 0
    for ai in A:
        ans = (ans + lcm * pow(ai, MOD - 2, MOD)) % MOD

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

# エラトステネスの篩(コピペ用)
table_len = 1010
prime_list = [] # 必要に応じて
isprime = [True] * (1010)
isprime[0] = isprime[1] = False
for i in range(table_len):
    if isprime[i]:
        for j in range(2*i, table_len, i):
            isprime[j] = False
        prime_list.append(i) # 必要に応じて

N = int(input())
As = list(map(int, input().split()))
factor_counts = [0] * len(prime_list)
big_factors = set() # 1000より大きな素数がAの素因数として含まれるとき、その素因数は一乗のみだから
for A in As:
    for i, p in enumerate(prime_list):
        count = 0
        while A % p == 0:
            A //= p
            count += 1
        factor_counts[i] = max(factor_counts[i], count)
        if A == 1:
            break
    else:
        big_factors.add(A)

A_lcm = 1
for p, count in zip(prime_list, factor_counts):
    A_lcm *= pow(p, count, MOD)
    A_lcm %= MOD

for p in big_factors:
    A_lcm *= p
    A_lcm %= MOD

ans = 0
for A in As:
    ans += A_lcm * pow(A, MOD - 2, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
def gcds(*numbers):
    from math import gcd
    from functools import reduce
    return reduce(gcd, numbers)

def lcms(*numbers):
    from math import gcd
    from functools import reduce
    def lcm_base(x, y):
        return x // gcd(x, y) * y
    return reduce(lcm_base, numbers)

def build_inv(N=10**5, P=10**9+7):
    inv = [0, 1]
    for i in range(2, N + 1):
        inv.append((-inv[P % i] * (P // i)) % P)
    return inv

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    invs = build_inv(10**6, MOD)
    target = lcms(*A)
    print(target*sum(map(lambda x: invs[x], A))%MOD)

    
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from functools import reduce
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


mod = 10**9+7


def prime(x):
    pf = defaultdict(int)
    for i in range(2, int(x**0.5)+1):
        while x % i == 0:
            pf[i] += 1
            x //= i
    if x > 1:
        pf[x] = 1
    return pf


def lcm(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] = max(xx[k], v)
    return xx


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a2 = list(map(prime, a))
    lcms = reduce(lcm, a2)
    lcmss = 1
    for k, v in lcms.items():
        lcmss = (lcmss*(k**v)) % mod
    ans = 0
    for aa in a:
        ans += lcmss*pow(aa,-1,mod)
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

b = []
for i in range(n):
    b.append(lcm // a[i])

print(sum(b) % MOD)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def rev(n,mod=(10**9+7)):
    ni = n
    nm = 1
    m2 = mod-2
    while m2 > 0:
        if m2&1:
            nm = (nm*ni)%mod
        m2 >>= 1
        ni = (ni**2)%mod
    return nm

#素因数分解
def factorization(n):
    d = dict()
    ni = n
    pn = 2
    t = 0
    while pn**2 <= n and ni > 1:
        if ni%pn == 0:
            t += 1
            ni //= pn
        else:
            if not t == 0:
                d[pn] = t
                t = 0
            if pn == 2:
                pn = 3
            else:
                pn += 2
    if t > 0:
        d[pn] = t
    if ni > 1:
        d[ni] = 1
    return d

def main():
    n = int(ipt())
    ans = 0
    a = [int(i) for i in ipt().split()]
    d = defaultdict(int)
    for i in a:
        ans += rev(i)
        di = factorization(i)
        for ki,vi in di.items():
            d[ki] = max(d[ki],vi)
        ans %= mod

    for ki,vi in d.items():
        ans *= pow(ki,vi,mod)
        ans %= mod

    print(ans)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, k**2):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Submission status: Accepted

Solution code:

from math import gcd
from functools import reduce


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


N = int(input())
X = list(map(int, input().split()))
total = reduce(lcm, X)
MOD = 10 ** 9 + 7

ans = 0
for v in X:
    ans += total * pow(v, MOD - 2, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


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

ctr = defaultdict(int)
buf = []
for n in X:
    d = prime_factor(n)
    buf.append(d)
    for key in d:
        ctr[key] = max(ctr[key], d[key])

total = 1
for key, val in ctr.items():
    total *= pow(key, val, MOD)
    total %= MOD

ans = 0
for i, n in enumerate(X):
    cur = total
    for key, val in buf[i].items():
        cur = cur * pow(pow(key, val, MOD), MOD - 2, MOD) % MOD

    ans += cur
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().rstrip().split()]

now=1
mod=10**9+7
def lcm(a,b):#最小公倍数
    ori_a=a
    ori_b=b
    while b!=0:
        a,b=b,a%b
    return (ori_a*ori_b)//a
  
for i in a:
  now=lcm(i,now)
# print(now)
print(sum([now//i for i in a])%mod)

Submission status: Accepted

Solution code:
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


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

m = 1000000007

prime_table = make_prime_table(10 ** 6)

lcm_factors = {}
for a in A:
    for p, e in prime_factorize(a):
        if p not in lcm_factors or lcm_factors[p] < e:
            lcm_factors[p] = e

lcm = 1
for p in lcm_factors:
    lcm *= pow(p, lcm_factors[p], m)
    lcm %= m

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

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
def main():
    n=I()
    lis=LI()
    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
    lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
    C=Counter([])
    for i in range(n):
        x=lists[i]
        for j in x.keys():
            C[j]=max(C[j],x[j])
    #print(C)
    
    ans=1
    '''for i in range(n):
        x=lists[i]
        y=1
        for j in C.keys():
            y=(y*pow(j,C[j]-x[j],mod))%mod
        #print(y%mod)
        ans=(ans+y)%mod
    print(ans%mod)'''
    invmod=0
    for i in range(n):
        invmod=(invmod+pow(lis[i]%mod,mod-2,mod))%mod
    for x in C.keys():
        ans=(ans*pow(x,C[x],mod))%mod
    print(ans*invmod%mod)
        
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import defaultdict

#素因数分解O(√n)
def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] += 1
    return res

    

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

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

MOD = 10**9+7
GCD = gcd(*A)

P = defaultdict(lambda: 0)

for i in range(N):
    factors = primeFactor(A[i])
    for k, v in factors.items():
        if v > P[k]:
            P[k] = v


P_mod = 1
for k in P.keys():
    P_mod = P_mod*(k**P[k])%MOD

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

print(ans)

Submission status: Accepted

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

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

l = 1
for i in a:
    l = lcm(l, i)

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

print(ans % 1000000007)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
so_list = [0 for i in range(10**6)]
mod = 10**9+7

def fac(n):
    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
            if so_list[i]<cnt:
              so_list[i]= cnt
    if temp!=1:
    #  print(temp)
      if so_list[temp]==0:
        so_list[temp]=1
for i in range(n):
  a1 = a[i]
  fac(a1)
l = 1
for i in range(len(so_list)):
  if so_list[i]!=0:
    l *= pow(i,so_list[i],mod)
    l %= mod
ans = 0
#print(l)
for i in a:
  t = pow(i,mod-2,mod)
  ans += (l*t)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)

for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM%mod,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%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(*numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(*a)

MOD = 10**9+7
ans = 0
for i in range(n):
    ans += l // a[i]
print(ans % MOD)

Submission status: Accepted

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

mod = 10**9 + 7
MAX = 1_000_000


def gen_primes(n):
    n = int(n**0.5) + 2
    is_prime = [True]*n
    is_prime[0] = is_prime[1] = False
    for i in range(2, n):
        if is_prime[i]:
            for j in range(2*i, n, i):
                is_prime[j] = False
    return [i for i, flag in enumerate(is_prime) if flag]


C = [0]*(MAX+1)
primes = gen_primes(MAX)


def prime_fact(n):
    cnt = 0
    for p in primes:
        if n % p:
            continue
        while n % p == 0:
            cnt += 1
            n //= p
        C[p] = max(C[p], cnt)
        cnt = 0
    if n != 1:
        C[n] = 1


for a in A:
    prime_fact(a)

lcm = 1
for i, c in enumerate(C):
    if c:
        lcm = lcm * pow(i, c, mod) % mod

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

Submission status: Accepted

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M
# print(val)

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

Submission status: Accepted

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M
# print(val)

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

Submission status: Accepted

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_dict=False):
        if x == 1:
            return {1:1} if return_dict else [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        if return_dict:
            result = {p: e for p, e in result}
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [sieve.factorize(a, return_dict=True) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M

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