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
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

# 高速素因数分解(√n)
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

lcd = dict()
for i in num:
  j = dict(factorization(i))
  for x,y in j.items():
    if not x in lcd.keys():
      lcd[x] = y
    else:
      lcd[x] = max(lcd[x],y)

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

# 高速素因数分解(√n)
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

lcd = dict()
for i in num:
  j = factorization(i)
  for x in j:
    if not x[0] in lcd.keys():
      lcd[x[0]] = x[1]
    else:
      lcd[x[0]] = max(lcd[x[0]],x[1])

lc = 1
for i,j in lcd.items():
  lc *= pow(i,j,mod)
  
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

Submission status: Accepted

Solution code:
def gcd(a,b):
    if a>b:
        return gcd(b,a)
    if a==0:
        return b
    return gcd(b-a*(b//a),a)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
s=1
for a in A:
    s=lcm(s,a)
ans=0
for a in A:
    ans+=s//a
print(ans%(10**9+7))

Submission status: Accepted

Solution code:
n = int(input())
nums = [int(i) for i in input().split()]
mod = 10 ** 9 + 7

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

LCM = 1
for num in nums:
    LCM = lcm(num, LCM)
LCM %= mod
# ans = 0
# for num in nums:
#     ans += (LCM // num) % mod
# print(ans % mod)
ans = 0
for num in nums:
    ans += LCM * pow(num, mod - 2, mod)
    ans %= mod

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
num = list(map(int, input().split()))
mod = 10**9+7

import fractions
lc = num[0]
for i in range(1, n):
    lc = lc * num[i] // fractions.gcd(lc, num[i])

lc %= mod    
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

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

Submission status: Accepted

Solution code:
from collections import deque, Counter, defaultdict
from functools import lru_cache
from itertools import permutations
from heapq import (
    heappush,
    heappop,
    heapreplace,
    heappushpop,
    heapify,
    merge,
    nlargest,
    nsmallest,
)
from statistics import mean, median, mode


def lcm(a, b):
    p = a * b
    while b:
        a %= b
        a, b = b, a
    return p // a


n = int(input())
a = list(map(int, input().split(" ")))
alcm = a[0]
for i in a:
    alcm = lcm(alcm, i)

tot = 0
for num in a:
    tot += alcm // num

print(tot % 1000000007)

Submission status: Accepted

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

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

n = int(input())
av = list(map(int, input().split(' ')))
alcm = 1
for i in av:
  alcm = lcm(alcm, i)

tot = 0
for i in range(n):
  tot += alcm // av[i]

print(tot % 1000000007)

Submission status: Accepted

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

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

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

L = 1

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

print(sum(L // a for a in A) % (10 ** 9 + 7))

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
A = lr()
lcm = 1
answer = 0
for a in A:
    coef =  a // gcd(lcm, a)
    answer *= coef
    lcm *= coef
    answer += lcm // a

print(answer%MOD)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
A = lr()
# lcm
lcm = 1
answer = 0
for a in A:
    coef =  a // gcd(lcm, a)
    answer *= coef
    lcm *= coef
    answer += lcm // a
    answer %= MOD

print(answer%MOD)

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

def make_primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass

def prime_decomposition(n): #素因数分解
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(i)
    i += 1
  if n > 1:
    table.append(int(n))
  return table

def make_divisors(n): #約数列挙
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def Topo_sort(x,y):
    co = cl.Counter(n for m in x.values() for n in m)
    S = cl.deque([i for i in range(y) if co[i] == 0])
    while S:
        n = S.popleft()
        yield n
        for i in x[n]:
            co[i] -= 1
            if co[i] <= 0:
                S.append(i)
    """
    if sum(co.values()) != 0:
        print(1)
        exit()
    else:
        print(0)
        exit()
    """
    #閉路検出(1が存在,0が存在しない)
# g = cl.defaultdict(set)に有向グラフを作成し(g[~] != ~ ,yはノード数) リストが帰ってくる

import fractions
from functools import reduce
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

n = onem()

a = l()

po = max(a)

ans = 0

al = 1

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

al %= mod

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

Submission status: Accepted

Solution code:
from fractions import gcd
def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m

m=10**9+7
n=int(input())
a=list(map(int,input().split()))
l=a[0]
for i in range(1,n):
  g=gcd(a[i],l)
  l=(a[i]//g)*l
b=0
for i in range(n):
  b=(b+gyakugen(a[i],m))%m
print((b*(l%m))%m)

Submission status: Accepted

Solution code:
import fractions

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

x=int(input())
a=list(map(int, input().split()))
ans=0
if x==1:
	print(1)
else:
	chk=lcm(a[0],a[1])
	for i in range(x):
		chk=lcm(chk,a[i])
	for i in range(x):
		ans=ans+(chk//a[i])
	print(ans%(10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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 i in range(n):
    ans+=(L*pow(A[i],mod-2,mod))%mod
print(ans%mod)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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])
L%=mod
ans=0
for i in range(n):
    ans+=L*pow(A[i],mod-2,mod)
print(ans%mod)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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])
L%=mod

coef=sum(pow(x,mod-2,mod) for x in A)
print(L*coef%mod)

Submission status: Accepted

Solution code:
from fractions import gcd
#from math import gcd
 
def lcm(m, n): return m * n // gcd(m, n)
 
n = int(input())
a = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
mulab = 1
for i in range(n):
    mulab = lcm(mulab, a[i])
 
mulab %= MOD
ans = 0
for i in range(n):
    #フェルマーの小定理
    ans = ans + mulab * pow(a[i], MOD-2, MOD)
    ans %= MOD
 
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from functools import reduce
import fractions

MOD = 1000000007  # type: int

GCD_CACHE = {}


def gcd(x, y):
    if (x, y) in GCD_CACHE:
        return GCD_CACHE[(x, y)]
    d = fractions.gcd(x, y)
    GCD_CACHE[(x, y)] = d
    return d


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


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def solve(N: int, A: "List[int]"):
    m = lcm(*A) % MOD
    sum = 0
    for a in A:
        sum = (sum + m*pow(a, MOD-2, MOD)) % MOD
    print(sum)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
def main():
    N=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    b=0
    c=1
    for a in A:
        c=c*a//gcd(c,a)
    c%=mod
    for a in A:
        b+=c*pow(a,mod-2,mod)
    print(b%mod)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import collections
nmax = 10**6+1
mod = 10**9+7

fac = [1]*nmax
finv = [1]*nmax
inv = [1]*nmax
def ncr_pre():
    for i in range(2,nmax):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod%i] * (mod//i) %mod
        finv[i] = finv[i-1] * inv[i] %mod

def factorize(n):
    b = 2
    fct = [(1,1)]
    while b * b <= n:
        cnt =0
        while n % b == 0:
            n //= b
            cnt +=1
        if cnt >=1:
            fct.append((b,cnt))
        b = b + 1
    if n > 1:
        fct.append((n,1))
    return fct

ncr_pre()

n = int(input())
a = list(map(int,input().split()))
co = collections.Counter()
for i in range(n):
    for num,cnt in factorize(a[i]):
        co[num] = max(co[num],cnt)

lcm= 1
for num,cnt in co.items():
    lcm *= num**cnt
    lcm%=mod

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

Submission status: Accepted

Solution code:
import math
MOD=10**9+7
MAX=10**6
sq_max=int(math.sqrt(MAX))

seive=[1 for _ in range(MAX+1)]
seive[0]=0
seive[1]=0
for i in range(sq_max+1):
  if seive[i]==0:
    continue
  for j in range(i*2,MAX+1,i):
    seive[j]=0

def factor(num):
  factordic={}
  for i in range(2,min([MAX+1,int(math.sqrt(num))+1])):
    if seive[i]==1 and num%i==0:
      factordic[i]=1
      num//=i
      while num%i==0:
        factordic[i]+=1
        num//=i
    if num==1:
      break
  else:
    factordic[num]=1
  return(factordic)


inv=[1,1]
for i in range(2, MAX+1):
  inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)

N=int(input())
ls=[int(s) for s in input().split()]
lcm={}
for num in ls:
  d=factor(num)
  for key,value in d.items():
    if key in lcm:
      lcm[key]=max(value,lcm[key])
    else:
      lcm[key]=value
lcmmod=1
for key,value in lcm.items():
  lcmmod=(lcmmod*(key**value))%MOD
invsum=0
for e in ls:
  invsum=(invsum+inv[e])%MOD
print((invsum*lcmmod)%MOD)

Submission status: Accepted

Solution code:
import math
MOD=10**9+7
MAX=10**6
sq_max=int(math.sqrt(MAX))

seive=[1 for _ in range(MAX+1)]
seive[0]=0
seive[1]=0
for i in range(sq_max+1):
  if seive[i]==0:
    continue
  for j in range(i*2,MAX+1,i):
    seive[j]=0

def factor(num):
  factordic={}
  for i in range(2,min([MAX+1,int(math.sqrt(num))+1])):
    if seive[i]==1 and num%i==0:
      factordic[i]=1
      num//=i
      while num%i==0:
        factordic[i]+=1
        num//=i
    if num==1:
      break
  else:
    factordic[num]=1
  return(factordic)


inv=[1,1]
for i in range(2, MAX+1):
  inv.append(MOD - inv[MOD % i] * (MOD // i) % MOD)

N=int(input())
ls=[int(s) for s in input().split()]
lcm={}
for num in ls:
  d=factor(num)
  for key,value in d.items():
    if key in lcm:
      lcm[key]=max(value,lcm[key])
    else:
      lcm[key]=value
lcmmod=1
for key,value in lcm.items():
  lcmmod=(lcmmod*(key**value))%MOD
invsum=0
for e in ls:
  invsum=(invsum+inv[e])%MOD
print((invsum*lcmmod)%MOD)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

MOD = 10**9+7

M = 10**3
primes = []
is_prime = [True] * (M+1)
for n in range(2,M+1):
    if not is_prime[n]: continue
    primes.append(n)
    for m in range(2*n,M+1,n): is_prime[m] + False

from collections import defaultdict
cmnd = defaultdict(int)

for a in A:
    for n in primes:
        i = 0
        while a % n == 0:
            i += 1
            a //= n
        cmnd[n] = max(cmnd[n], i)
    if a > 1: cmnd[a] = max(cmnd[a], 1)

lcm = 1
for k,v in cmnd.items():
    for i in range(v):
        lcm = (lcm * k) % MOD

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

print(ans)

Submission status: Accepted

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

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for x in a:l = lcm(l, x)
    ans = 0
    for x in a:
        ans+=l//x

    print(ans%1000000007)
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    gcdA = A[0]
    lcmA = A[0]
    for i in range(1, N):
        gcdA = gcd(lcmA, A[i])
        lcmA = (lcmA * A[i]) // gcdA
    lcmA %= mod
    Ans = 0
    for a in A:
        Ans += (lcmA * pow(a, mod - 2, mod)) % mod
        Ans %= mod
    print(Ans)


    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

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

t=0
for i in range(N):
  t=(t+l*pow(A[i],M-2,M))%M

print(t%M)

Submission status: Accepted

Solution code:
# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


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


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
lcm_val = A[0]
for a in A[1:]:
    lcm_val = lcm(lcm_val, a)

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

Submission status: Accepted

Solution code:
import functools
"""最大公約数"""
def gcd(a,b):
    import fractions
    return fractions.gcd(a,b)

"""最小公倍数"""
def lcm(a,b):
    f = gcd(a,b)
    return a*b//f

def m(nums):
    return functools.reduce(lcm, nums)

def main():
    n = int(input())
    A = list(map(int,input().split()))
    mod = 10**9+7
    l = m(A)
    res = 0
    print(sum(l// i for i in A) % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    x = reduce(lcm, a)
    print(sum(x // i for i in a) % mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n = int(input())
a = [int(x) for x in input().split()]
am = max(a)
mod = 10**9+7
if n==1:
    print(1)
    sys.exit()
li = [0]*(am+1)
lcm = 1
for k in range(n):
    z = a[k]
    for i in range(2,int(z**0.5)+1):
        x = 0
        while z%i==0:
            x += 1
            z//=i
        li[i] = max(li[i],x)
    if z!=1 and li[z]==0:
        li[z] = 1

for i in range(2,am+1):
    if li[i]>0:
        lcm = lcm * i**li[i] % mod

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

Submission status: Accepted

Solution code:
#152_E
from fractions import gcd
from functools import reduce

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

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

print(sum(x // ai for ai in a) % mod)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
from fractions import gcd
def lcm(list):
    num = 1
    for x in list:
        num = num//gcd(num, x)*x
    return num%mod

def Pow(a,n):
    if n == 0: return 1
    if n%2 == 0:
        return (Pow(a, n//2))**2%mod
    else:
        return Pow(a, n-1)*a%mod

N = int(input())
A = list(map(int, input().split()))
M = lcm(A)
R = [0]*N
for i in range(N):
    R[i] = Pow(A[i],mod-2)
ans = 0
for i in range(N):
    ans = (ans+M*R[i])%mod
print(ans)

Submission status: Accepted

Solution code:
mod = 10**9 + 7
def iip(listed = False):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret

def inv(n, mod):
    return power(n, mod-2)

def power(n, p):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p//2) ** 2) % mod
    if p % 2 == 1:
        return (n * power(n, p-1)) % mod

def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret

n = iip()
A = iip(listed=True)

def main():
    ss = []
    for a_i in A:
        for s in ss:
            if a_i % s == 0:
                a_i //= s

        ss.extend(soinsuu_bunkai(a_i))

    #print(ss)
    all = 1
    for s in ss:
        all *= s
        all %= mod

    ans = 0
    for a_i in A:
        ans += (all * inv(a_i, mod)) % mod
        ans %= mod
    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n <= 1:
    return [],[],[]
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  isprime = [0]*(n+1)
  isprime[2] = 1
  min_factor = [0 if i%2 != 0 else 2 for i in range(n+1)]
  while True:
    p = data[0]
    prime.append(p)
    isprime[p] = 1
    pdata,data = data,[]
    for e in pdata:
      if e%p != 0:
        data.append(e)
      else:
        min_factor[e] = p
    if limit <= p:
      for i in data:
        isprime[i] = 1
        min_factor[i] = i
      return prime + data,isprime,min_factor
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
ma = max(a)
data,isprime,min_factor = prime_table(ma)
prime = [0] * (ma+1)
for i in a:
  if i == 1:
    continue
  d = defaultdict(int)
  while isprime[i] == 0:
    d[min_factor[i]] += 1
    i = i // min_factor[i]
  d[i] += 1
  for j,k in d.items():
    prime[j] = max(prime[j],k)
lcm = 1
for i in range(ma+1):
  if prime[i] != 0:
    lcm = (lcm*pow(i,prime[i],MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

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

mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
L = a[0]
for i in a:
    L = lcm(L,i)
    
ans = 0
for i in a:
    ans += (L // i )
print(ans % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce


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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    com = lcm_list(A) % MOD
    ans = 0
    for a in A:
        ans += com * pow(a, MOD - 2, MOD)
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

l %= mod

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

ans = 0
for e in a:
    ans += l * inv[e]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

l %= mod

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

MOD = 1000000007

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)

Submission status: Accepted

Solution code:
MAX_PRIME = 10**3
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y
def moddiv(a, b):
    _, inv, _ = extGCD(b, law)
    return a * inv % law

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

ans = 0
l = {}
lmod = 1
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            ans *= p ** c
            lmod *= p ** c
            ans %= law
            lmod %= law
            l[p] = c
        elif c > l[p]:
            ans *= p ** (c - l[p])
            lmod *= p ** (c - l[p])
            ans %= law
            lmod %= law
            l[p] = c
    b = moddiv(lmod, x)
    ans += b
    ans %= law
print(ans)

Submission status: Accepted

Solution code:
def pow(x, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        n >>= 1
    return ret
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
mod = 10**9+7
N = int(input())
a = list(map(int,input().split()))
g = a[0]
l = g
for i in range(1,N):
    g = gcd(l, a[i])
    l = (l*a[i])//g
ans = 0
l %= mod
for i in range(N):
    tmp = (pow(a[i], mod-2, mod)*l)%mod
    ans = (ans+tmp)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc152/tasks/abc152_e
# 見た瞬間にわかってしまった天才だ

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def factorization(n: int):
    if n == 1:
        return []  # 1は素数ではない
    # 素因数分解
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 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


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


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


N = read_a_int()
A = read_ints()

flat = defaultdict(lambda: 0)  # 素数がkey
for a in A:  # modで演算できるようにするか掛け算を実際には行わずに保持しておく必要がある。
    tmp = factorization(a)
    for k, v in tmp:
        flat[k] = max(flat[k], v)

flat_mod = 1
for k, v in flat.items():
    flat_mod *= pow(k, v, MOD)
    if flat_mod >= MOD:
        flat_mod %= MOD

ans = 0
for a in A:
    ans += flat_mod * ret_inv(a, MOD)
    if ans >= MOD:
        ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
import collections
from collections import defaultdict

# mod. m での a の逆元 a^{-1} を計算する
# b * a^{-1} (mod m)を計算したい場合はb * modinv(a, m) % m
def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u
    
# 途中計算でmodを計算する高速な累乗計算
def pow_k_mod(x, n, m):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m
    
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

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

factor = defaultdict(lambda: -1)
for i in range(N):
    c = collections.Counter(prime_factorize(A[i]))
    for k, v in c.items():
        factor[k] = max(factor[k], v)

lcm = 1
for k, v in factor.items():
    lcm *= pow_k_mod(k, v, int(1e9+7))
    lcm %= int(1e9+7)

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))

Submission status: Accepted

Solution code:
import math

def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def prime_fuctorization(n):
  result = {}
  count = 0
  while n % 2 == 0:
    n //= 2
    count += 1
    
  if count != 0:
    result[2] = count
  
  for i in range(3, n, 2):
    count = 0
    while n % i == 0:
      n //= i
      count += 1
    
    if count != 0:
      result[i] = count
      
    if math.sqrt(n) <= i:
      break
      
  if n != 1:
    result[n] = 1
    
  return result
    
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))

soinsu = []
result = {}
for i in range(n):
  dic = prime_fuctorization(a[i])
  soinsu.append(dic)
  
  for k in dic.keys():
    item = dic[k]
    if item >= result.get(k, 0):
      result[k] = item
      
m = 1
tmp = 1
for k, v in result.items():
  m *= pow_k(k, v, MOD)
  tmp *= k ** v
  m %= MOD
  
ans = 0
for i in range(n):
  ans += m * pow_k(a[i], MOD-2, MOD)
  ans %= MOD
  
print(ans)