Problem:


Score : 500 points

Problem Statement

Given are N positive integers A_1,...,A_N.

Consider positive integers B_1, ..., B_N that satisfy the following condition.

Condition: For any i, j such that 1 \leq i < j \leq N, A_i B_i = A_j B_j holds.

Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N.

Since the answer can be enormous, print the sum modulo (10^9 +7).

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo (10^9 +7).

Sample Input 1

3
2 3 4

Sample Output 1

13

Let B_1=6, B_2=4, and B_3=3, and the condition will be satisfied.

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

Print the sum modulo (10^9+7).



Sample input:
3
2 3 4


Sample output:
13

Submission status: Accepted

Solution code:
from fractions import gcd

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

t = 1
mod = 10**9 + 7

for i in A:
    t *= i // gcd(t,i)

ans = sum(t//i for i in A)

print(ans % mod)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


# 最小素因数を求める（エラトステネスの篩の亜種？）
def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)

    # エラトステネスのふるい
    def sieve_of_eratosthenes(n):
        sieve = [True] * n
        for i in range(3, int(n ** 0.5) + 1, 2):
            if sieve[i]:
                sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
        return [i for i in range(3, n, 2) if sieve[i]]

    for i in sieve_of_eratosthenes(int(n ** 0.5) + 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i - 1) // (2 * i) + 1)
    return sieve


# 素因数分解
def prime_factorize(n):
    a = [1]
    while n != 1:
        b = table[n]
        a.append(b)
        n //= b
    return a


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

table = min_factor(10 ** 6)
dic = {}

for i in A:
    for key, value in Counter(prime_factorize(i)).items():
        # print(key, value)
        if dic.get(key):
            if dic[key] < value:
                dic[key] = value
        else:
            dic[key] = value

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

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)

N = INT()
A = LIST()

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

B = [0] * N
for i, a in enumerate(A):
    B[i] = fermat(l, a, MOD)

ans = 0
for b in B:
    ans += b
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
from fractions import*
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)

Submission status: Accepted

Solution code:
from fractions import gcd

N = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
res = 0
for x in a:
  l = x * l // gcd(x, l)
l %= mod
for x in a:
  res += l * pow(x, mod - 2, mod)
  res %= mod
print(res)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
def extgcd(a,b):
  r=[1,0,a]
  w=[0,1,b]
  while w[2]!=1:
    q=r[2]//w[2]
    r2=w
    w2=[r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
    r=r2
    w=w2
  return [w[0],w[1]]
def mod_inv(a,m):
  x=extgcd(a,m)[0]
  return (m+x%m)%m

def primes(n):
  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
  return [i for i in range(n+1) if is_prime[i]]

prime=primes(int(10**3)+1)

def fact2(n):
  l=prime
  L=[]
  for i in range(len(l)):
    ct=0
    while n%l[i]==0:
      n=n//l[i]
      ct+=1
    if ct!=0:
      L.append((l[i],ct))
    if n==1:
      break
  if n!=1:
    L.append((n,1))
  return L

n=int(input())
a=list(map(int,input().split()))
l=[0 for i in range(10**6)]
mod=10**9+7
for i in range(n):
  x=fact2(a[i])
  for j in range(len(x)):
    l[x[j][0]]=max(l[x[j][0]],x[j][1])
lcm=1
for i in range(2,10**6):
  lcm*=(i**l[i])
  lcm%=mod
ans=0
for i in range(n):
  ans+=lcm*mod_inv(a[i],mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions
 
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)
 
N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]
 
cand = lcm_list(As)
 
sum = 0
 
for num in As:
    sum = sum + cand // num
 
print(sum % (10**9 + 7))

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = 1
for a in A:
    L *= a // gcd(L, a)

L %= mod

print(sum(L * pow(a, mod - 2, mod) for a in A) % mod)

Submission status: Accepted

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**3)
for i in range(2,10**3):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**3,i):
        is_prime[j]=False

LCM=defaultdict(int)
for n in A:
    for p in primes:
        tmp=0
        while n%p==0:
            tmp+=1
            n//=p
        LCM[p]=max(LCM[p],tmp)
    if n!=1:
        LCM[n]=max(LCM[n],1)
l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

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

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions
 
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)
 
N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]
 
cand = lcm_list(As)
 
sum = 0
 
for num in As:
    sum = sum + cand // num
 
print(sum % (10**9 + 7) )

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


# 最小素因数を求める（エラトステネスの篩の亜種？）
def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i - 1) // (2 * i) + 1)
    return sieve


# 素因数分解
def prime_factorize(n):
    a = []
    while n != 1:
        b = table[n]
        a.append(b)
        n //= b
    return a


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

table = min_factor(10 ** 6)
dic = {}

for i in A:
    if i == 1:
        continue

    for key, value in Counter(prime_factorize(i)).items():
        # print(key, value)
        if dic.get(key):
            if dic[key] < value:
                dic[key] = value
        else:
            dic[key] = value


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

answer = sum(lcm * pow(i, mod - 2, mod) for i in A) % mod
print(answer)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions

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)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

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

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = 1
for a in A:
    L *= a // gcd(L, a)

L %= mod

print(sum(L * pow(a, mod - 2, mod) % mod for a in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
n = int(input())
a = [int(x) for x in input().split()]
sum = 0
G=1
for elem in a:
    G=lcm(G,elem)
for elem in a:
  sum+=G//elem
print(sum%1000000007)

Submission status: Accepted

Solution code:
#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)

#べき乗関数powを使った逆元の計算(modinvよりもPythonでは高速、PyPyだと遅い)
def modinv2(a,m):
    return pow(a,m-2,m)


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

if N == 1:
    ans = 1

else:

    inv = modinv2(A[0],P)
    g = A[0]
    invlist = []
    seki = A[0]%P

    for i in range(1,N):
        inv = (inv+modinv2(A[i],P))%P
        seki = seki*A[i]%P

    g = gcd(A[0],A[1])
    l = A[0]//g*A[1]
    cc = modinv2(g,P)
    for i in range(2,N):
        g = gcd(l,A[i])
        l = l//g*A[i]
        cc = cc*modinv2(g,P)%P

    ans = (inv*seki%P)*cc%P

print(ans)

Submission status: Accepted

Solution code:
#べき乗関数powを使った逆元の計算(modinvよりもPythonでは高速、PyPyだと遅い)
def modinv(a,m):
    return pow(a,m-2,m)

#n以下の素数列挙(O(nlog(n))
def primes(n):
    ass = {}
    is_prime = [True for _ in range(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
        #i**2から始めてOK
        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[i] = 0
    return ass

#[[素因数,数]]を出力
def fctr1(n): 
    f = []
    c = 0
    for i in range(2,int(n**0.5)+2):
        while n%i == 0:
            c += 1
            n = n//i
        if c !=0:
            f.append([i,c])
            c = 0
    if n != 1:
        f.append([n,1])
    return f

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

e = primes(10**6+7)
inv = 0
P = 10**9+7

for i in range(N):
    inv = (inv+modinv(A[i],P))%P
    l = fctr1(A[i])
    for j in range(len(l)):
        e[l[j][0]] = max(e[l[j][0]],l[j][1])

ans = 1
for k in e.keys():
    if e[k] != 0:
        for i in range(e[k]):
            ans = ans*k%P
ans = ans*inv%P

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
n = int(input())
A = list(map(int,input().split()))

mod = 10 ** 9 + 7
lcm = reduce(lambda x,y: x*y//gcd(x,y), A)
# print(lcm)
ans = sum(lcm//x for x in A)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read


def min_factor(n):
    sieve = list(range(n + 1))
    sieve[2::2] = [2] * (n // 2)
    for i in range(3, int(n ** 0.5) + 2, 2):
        if sieve[i] == i:
            sieve[i * i::2 * i] = [i] * ((n - i * i - 1) // (2 * i) + 1)
    return sieve


# 素因数分解
def prime_factorize(n):
    a = []
    while n != 1:
        a.append(table[n])
        n //= table[n]
    return a


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

table = min_factor(10 ** 6)
dic = {}

for i in A:
    if i == 1:
        continue

    tmp = Counter(prime_factorize(i))

    for key, value in tmp.items():
        # print(key, value)
        if dic.get(key):
            if dic[key] < value:
                dic[key] = value
        else:
            dic[key] = value


lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)

Submission status: Accepted

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

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

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

Submission status: Accepted

Solution code:
#coding:utf-8

from fractions import gcd
n = int(input())
a = list(map(int, input().split(' ')))

mod = 10 ** 9 + 7

#最小公倍数を取得
g = a[0]
for num in a[1:]:
    g = g * num // gcd(num, g)

ans = 0
#計算後なのでmodオッケー
l = g % mod
for num in a:
    ans += l * pow(num, mod-2, mod)
    ans %= mod
print(ans % mod)

Submission status: Accepted

Solution code:
import math
from fractions import gcd
from functools import reduce

DIV=10**9+7

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

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

ans=sum(list(map(lambda x:g//x,A)))
print(ans%DIV)

Submission status: Accepted

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

if N == 1:
  print(1)
  exit()

import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

def listgcd(L):
  p = prime(L[0])
  for i in range(1, len(L)):
    q = prime(L[i])
    for n in q:
      if n in p:
        p[n] = max(p[n], q[n])
      else:
        p[n] = q[n]
  return p

def listgcdmod(L, MOD):
  p = listgcd(L)
  t = 1
  for n in p:
    t = t * pow(n, p[n]) % MOD
  return t

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L

t = listgcdmod(A, MOD)
inv = Inv(MOD)
ans = 0
for i in range(N):
  ans = (ans + t * inv.invx(A[i])) % MOD
print(ans)

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
  for i in a:
      b+=pow(i,mod-2,mod)


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

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


  print(L*b%mod)

  
main()

Submission status: Accepted

Solution code:
import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))

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
  for i in a:
      b+=pow(i,mod-2,mod)


  L=a[0]
  def lcm(x,y):
      return x//gcd(x,y)*y

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


  print(L*b%mod)

  
main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

mod = 10 ** 9 + 7

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

n = int(input())
lis = list(map(int,input().split()))
now = reduce(lcm,lis)

print(sum(list(map(lambda x:now//x,lis)))%mod)

Submission status: Accepted

Solution code:
import fractions

mod = 10**9 + 7;

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

l = 1
for i in A:
  l = l * i // fractions.gcd(l, i)

sum = 0
for i in A:
  sum += l // i

print(int(sum % mod))

Submission status: Accepted

Solution code:
#逆元

from fractions import gcd

n=int(input())

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

b=0
for i in a:
    b+=pow(i,mod-2,mod)


L=a[0]
def lcm(x,y):
    return x//gcd(x,y)*y

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


print(L*b%mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = reduce(lambda x,y: y//gcd(x,y)*x, A)

answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd
from functools import reduce

N,*A = map(int,read().split())

MOD = 10 ** 9 + 7

lcm = reduce(lambda x,y: x//gcd(x,y)*y, A)

answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import fractions

mod = 10**9 + 7;

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

l = 1
for i in A:
  l = l * i // fractions.gcd(l, i)

sum = 0
for i in A:
  sum += l // i

print(sum % mod)

Submission status: Accepted

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

MOD=10**9+7

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

LCM=defaultdict(int)
def f(n):
    tmp=0
    p=2
    while n%p==0:
        tmp+=1
        n//=p
    LCM[p]=max(LCM[p],tmp)
    p=3
    while p*p<=n:
        tmp=0
        while n%p==0:
            tmp+=1
            n//=p
        LCM[p]=max(LCM[p],tmp)
        p+=2
    if n>1:
        LCM[n]=max(LCM[n],1)

for a in A: f(a)

l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

ans=0
for a in A:
    ans+=l*inv[a]%MOD

print(ans%MOD)

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# coding: utf-8

import math
from fractions import gcd
from functools import reduce

MOD = 10**9 + 7

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

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

ans = sum(list(map(lambda x:g//x, a)))
print(ans%MOD)

Submission status: Accepted

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

from fractions import gcd
from functools import reduce

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

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

lcma = lcm_list(an)
ans = 0
for i in range(n):
    ans += (lcma//an[i])
mod=10**9+7
print(ans%mod)

Submission status: Accepted

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

MOD=10**9+7

LCM=defaultdict(int)
def f(n):
    tmp=0
    p=2
    while n%p==0:
        tmp+=1
        n//=p
    LCM[p]=max(LCM[p],tmp)
    p=3
    while p*p<=n:
        tmp=0
        while n%p==0:
            tmp+=1
            n//=p
        LCM[p]=max(LCM[p],tmp)
        p+=2
    if n>1:
        LCM[n]=max(LCM[n],1)

for a in A: f(a)

l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

n = int(input())
aaa = list(map(int, input().split()))
lcm = reduce(lambda a, b: a * b // gcd(a, b), aaa)
print(sum(lcm // a for a in aaa) % 1000000007)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
from fractions import gcd
mod = 10**9+7
g = A[0]
for a in A[1::]:
  g = g*a//gcd(g,a)

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

Submission status: Accepted

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

MOD=10**9+7

LCM=defaultdict(int)
def f(n):
    ret=defaultdict(int)
    p=2
    while n%p==0:
        ret[p]+=1
        n//=p
    LCM[p]=max(LCM[p],ret[p])
    p=3
    while p*p<=n:
        while n%p==0:
            ret[p]+=1
            n//=p
        LCM[p]=max(LCM[p],ret[p])
        p+=2
    if n>1:
        ret[n]=1
        LCM[n]=max(LCM[n],ret[n])
    return ret

F=[]
for a in A:
    F.append(f(a))

l=1
for p,n in LCM.items():
    l=l*pow(p,n,MOD)%MOD

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


N = int(input())
A = list(map(int, input().split()))
lcm = lambda x, y: x*y//gcd(x, y)
l = 1
for a in A:
    l = lcm(l, a)
ans = 0
MOD = 10**9+7
for a in A:
    ans += l // a
print(ans % MOD)

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = 1
for a in A:
    L *= a // gcd(L, a)

print(sum(L // a for a in A) % mod)

Submission status: Accepted

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

N = int(input())
a_list = list(map(int, input().split()))
x = a_list[0]
for i in range(1, N):
    x = x * a_list[i] // fractions.gcd(x, a_list[i])
mod = 10 ** 9 + 7
t = 0
for a in a_list:
    b = x // a
    t += b

ans = t % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

dic={}
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

# print(factorization(12))
for i in range(n):
    tmp=factorization(a[i])
    for j in range(len(tmp)):
        if not tmp[j][0] in dic:
            dic[tmp[j][0]]=tmp[j][1]
        else:
            dic[tmp[j][0]]=max(dic[tmp[j][0]],tmp[j][1])
l=1
for i in dic.keys():
    l*=i**dic[i]
    l%=mod
# print(l)
ans=0
for i in range(n):
    ans+=l*pow(a[i],mod-2,mod)
    ans%=mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

lcm = lambda a, b: a * b // gcd(a, b)
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = reduce(lcm, A)
print(sum(L // a for a in A) % mod)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

def main():
    lcm = lambda a, b: a * b // gcd(a, b)
    mod = 10 ** 9 + 7

    N, *A = map(int, open(0).read().split())

    L = reduce(lcm, A)
    print(sum(L // a for a in A) % mod)

main()

Submission status: Accepted

Solution code:
from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)

ans = sum(lcm // a for a in aaa) % MOD
print(ans)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

mod = 10**9 + 7

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

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

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

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

print(ans)

Submission status: Accepted

Solution code:
import fractions
 
N = int(input())

def LI():
  return [int(s) for s in input().split()]

A_s = LI()
mod = 10**9 + 7

#l = lcm_list(A_s)
l = 1
for num in A_s:
    l = l * num // fractions.gcd(l,num)

count = 0
for a in A_s:
  count+=l//a
  
print(count % mod)

Submission status: Accepted

Solution code:
from fractions import gcd

n = int(input())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
lcm = aaa[0]
for a in aaa[1:]:
    lcm = lcm * a // gcd(lcm, a)
lcm %= MOD

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

Submission status: Accepted

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

# 参考：https://qiita.com/aki-takano/items/a43fac70b702d4f22d7e
def lcm(a):
    from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

L = lcm(A)
B = []
for a in A:
    B.append(L // a)

print(sum(B) % 1000000007)

Submission status: Accepted

Solution code:
n = int(input())

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

mod = 10**9 + 7

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)

x = lcm_list(a)
# print(x)

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

print(int(ans)%mod)

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

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


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


n = int(input())
l = [int(_) for _ in input().split()]
x = lcm_list(l)
ans = 0
for i in range(n):
    ans += x // l[i]
ans %= (10**9 + 7)
print(ans)

Submission status: Accepted

Solution code:
#逆元

from fractions import gcd

n=int(input())

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

b=0
for i in a:
    b+=pow(i,mod-2,mod)


L=a[0]
def lcm(x,y):
    return x//gcd(x,y)*y

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


print(L*b%mod)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd

MOD = 10**9+7

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

def main():
    N = int(input())
    a = [int(i) for i in input().split()]

    lcm = reduce(lcm_base, a, 1)
    
    ans = 0
    for i in a:
        ans += lcm // i

    print(ans % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

#arr：最小公倍数の対象とする配列
MOD = 10**9 + 7
def lcm(arr):
    primes = {}
    for val in arr:
        p = 2
        while p * p <= val:
            if val % p == 0:
                cnt = 0
                while val % p == 0:
                    cnt += 1
                    val //= p
                if p not in primes:
                    primes[p] = cnt
                else:
                    primes[p] = max(cnt, primes[p])
            p += 1
     
        if val != 1:
            if val not in primes:
                primes[val] = 1
    lcma = 1
    for p in primes:
        lcma = lcma * pow(p, primes[p], MOD) 
    return lcma

b = lcm(arr)

ans=0
for i in range(n):
    ans+= b*pow(arr[i],MOD-2,MOD)

print(ans%MOD)

Submission status: Accepted

Solution code:
#逆元しない場合

from fractions import gcd

n=int(input())

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




L=a[0]
def lcm(x,y):
    return x//gcd(x,y)*y

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


print(sum([L//i for i in a])%mod)

Submission status: Accepted

Solution code:
M=10**9+7
mod =M
import sys
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
NNN = (10**6)
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

from collections import defaultdict
N=input()
xs = list(map(int, input().split()))
ys = []
d = defaultdict(int)
for x in xs:
    ps = prime_decomposition(x)
    psd = defaultdict(int)
    for p, c in ps:
        psd[p] = c
        d[p] = max(d[p], c)
    ys.append(psd)
g=1
for p in d:
    g=mul(g,p**(d[p])%M)%M
r=0
for x in xs:
    r = (r+mul(g,inverse[x]))%M
print(r%M)

Submission status: Accepted

Solution code:
import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = (i * tmp)//fractions.gcd(i, tmp)

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)

Submission status: Accepted

Solution code:
import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = (i//fractions.gcd(i, tmp)) * tmp

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)