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 collections import Counter

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

primes = [
  2,  3,  5,  7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
 71, 73, 79, 83, 89, 97,101,103,107,109,113,127,131,137,139,149,151,157,163,
167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,
271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,
389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,
503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,
631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,
757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,
883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997,
1009
]

def prime_factorize(n):
    res = []
    i = 0
    while primes[i] * primes[i] <= n:
        if n % primes[i] == 0:
            res.append(primes[i])
            n //= primes[i]
        else:
            i += 1
    if n != 1:
        res.append(n)
    return res


lcm_factors = Counter()
for ai in a:
    prime_factors = prime_factorize(ai)
    counter = Counter(prime_factors)
    for k, v in counter.items():
        if k in lcm_factors:
            lcm_factors[k] = max(lcm_factors[k], v)
        else:
            lcm_factors[k] = v

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

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

print(ans)

Submission status: Accepted

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

mod = 10 ** 9 + 7

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

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

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

l %= mod
B = 0
for i in range(len(A)):
    B += l * pow(A[i], mod - 2, mod)
    B %= mod

print(B)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

def divs(n):
  dic={}
  if n==2:
    dic={}
    dic[2]=1
    return dic
  elif n==3:
    dic={}
    dic[3]=1
    return dic
  for i in range(2,int(n**0.5)+1):
    if n%i==0:
      dic[i]=1
      n=n//i
      while n%i==0:
        dic[i]+=1
        n=n//i
  if n!=1:
    dic[n]=1
  return dic        

mod=10**9+7
n=int(input())
arr=list(map(int,input().split()))
l=collections.defaultdict(int)
ans=0
for i in range(n):
  ans+=pow(arr[i],mod-2,mod)
  ans%=mod
  d=divs(arr[i])
  for keys in d.keys():
    l[keys]=max(l[keys],d[keys])
for keys in l.keys():
  ans*=pow(keys,l[keys],mod)
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

def factorize(x):
    vec = {}
    d = 2
    while d * d <= x:
        if x % d == 0:
            if d not in vec:
                vec[d] = 0
            vec[d] += 1
            x //= d
        else:
            d += 1
    if x > 1:
        if x not in vec:
            vec[x] = 0
        vec[x] += 1
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

l = {}
for x in a:
    f = factorize(x)
    for k in f:
        l[k] = max(l[k], f[k]) if k in l else f[k]
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)

Submission status: Accepted

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

l = {}
for x in a:
    f = factorize(x)
    for k in f:
        l[k] = max(l[k], f[k]) if k in l else f[k]
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)

Submission status: Accepted

Solution code:
# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

fact = [factorize(x) for x in a]

fset = set()
for f in fact:
    fset.update(f.keys())

l = {k: 0 for k in fset}
for f in fact:
    for k in f:
        l[k] = max(l[k], f[k])
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)

Submission status: Accepted

Solution code:
# cook your dish here
def gcd(a,b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
  
def lcm(a,b): 
    return (a*b) // gcd(a,b) 
  
n = int(input())
arr=input()
a=list(map(int,arr.split(' ')))
l = a[0]
ans = 0
for i in range(n):
    l = lcm(l, a[i])
for i in range(n):
    ans = ans + l//a[i]
print(ans%1000000007)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce, partial
import sys


def input():
    return sys.stdin.readline()[:-1]

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

def func(a, b, l):
	mod = 10**9 + 7
	return (a +  l*modinv(b, mod)) % mod

def modinv(a, b):
	return pow(a,b-2,b)

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

	l = reduce(lcm, A) % mod
	A = (0,) + A
	
	ans = reduce(partial(func, l=l), A)
	print(ans)
	

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from fractions import gcd
N = input()
A = list(map(int, input().split(" ")))
def lcm(x, y):
    return (x * y) // gcd(x, y)
tmp = 1
for i in A:
    tmp = lcm(tmp, i)
print(sum([tmp // i for i in A]) % (10**9 + 7))

Submission status: Accepted

Solution code:
from fractions import gcd


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

lcm = 1
for a in A:
    lcm = lcm * a // gcd(lcm, a)
lcm %= MOD

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def mod_inv(a, m):
    return pow(a, m-2, m)


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

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

ans = 0
for a in A:
    ans += LCM * mod_inv(a, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def mod_inv(a, m):
    return pow(a, m-2, m)


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

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

# ans = LCM * sum([mod_inv(a, MOD) for a in A]) % MOD
ans = 0

for a in A:
    ans += LCM * mod_inv(a, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

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

from fractions import gcd


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


def mod_inv(a, m):
    return pow(a, m-2, m)


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

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

# ans = LCM * sum([mod_inv(a, MOD) for a in A]) % MOD
ans = 0
for a in A:
    ans += LCM * mod_inv(a, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def mod_inv(a, m):
    return pow(a, m-2, m)


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

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

# ans = LCM * sum([mod_inv(a, MOD) for a in A]) % MOD
ans = 0
for a in A:
    ans += LCM * mod_inv(a, MOD) % MOD
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


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


def mod_inv(a, m):
    return pow(a, m-2, m)


MOD = 10 ** 9 + 7

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


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

ans = _lcm * sum([mod_inv(s, MOD) for s in A]) % MOD

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


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

ans = _lcm * sum([pow(s, MOD - 2, MOD) for s in A]) % MOD

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


_lcm = 1
for a in A:
    # _lcm = lcm(_lcm, a)
    _lcm = _lcm * a // gcd(_lcm, a)

ans = _lcm * sum([pow(s, MOD - 2, MOD) for s in A]) % MOD

print(int(ans % MOD))

Submission status: Accepted

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7

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

lcm = 1
for s in A:
    lcm = s * lcm // gcd(lcm, s)

ans = lcm * sum([pow(s, mod - 2, mod) for s in A]) % mod

print(int(ans % mod))

Submission status: Accepted

Solution code:
from fractions import gcd
#from math import gcd
import numpy as np
import sys
input = sys.stdin.readline
mod = 10**9+7

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

lcm = 1
for s in A:
    lcm = s*lcm//gcd(lcm, s)

ans = lcm*sum([pow(s, mod-2, mod) for s in A]) % mod
#ans = sum([lcm//s % mod for s in A]) % mod

print(int(ans%mod))

Submission status: Accepted

Solution code:
def main():
  def sieve(n):
    prime=[]
    limit=n*0.5
    data=[i+1 for i in range(1,n)]
    p_append=prime.append
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        p_append(p)
        data=[e for e in data if e%p!=0]
        
  prime=sieve(1000)
  import sys
  import numpy as np
  input=sys.stdin.readline
  mod=10**9+7
  
  n=int(input())
  num=list(map(int,input().split()))
  num_copy=np.array(num)
  
  lcm=1
  for p in prime:
    while np.any(num_copy%p==0):
      num_copy[num_copy%p==0]//=p
      lcm *= p
      lcm %= mod
  
  for i in set(num_copy.tolist()):
    lcm *= i
    lcm %= mod
    
  #print(lcm,num)
  ans=0
  for i in range(n):
    ans += lcm * pow(num[i] ,mod-2 ,mod)
    ans %= mod 
    #print(ans)
  print(ans)
  
if  __name__=='__main__':
  main()

Submission status: Accepted

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

def main():
	n, *a = map(int, open(0).read().split())
	mod = 10 ** 9 + 7
	lcm = 1
	for x in a:
		lcm = lcm * x // gcd(lcm, x)
	lcm %= mod
	ans = sum(pow(x, mod - 2, mod) for x in a) % mod
	print(ans * lcm % mod)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from functools import reduce

def solve():
    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

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

    lcmA = reduce(lcm, As)
    #print('lcmA:', lcmA)

    ans = 0
    for A in As:
        ans += lcmA // A
    ans %= MOD

    print(ans)

solve()

Submission status: Accepted

Solution code:
###提出 #10048385

n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)

#頭良すぎて草

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    minPFs = getMinPFs(maxA)

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    cntP = Counter()
    for A in As:
        PFs = getPrimeFactors(A, minPFs)
        for key, num in Counter(PFs).items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(maxA, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()

Submission status: Accepted

Solution code:
from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

    def getPrimeFactors(x):
        anss = []
        while x%2 == 0:
            anss.append(2)
            x //= 2
        for d in range(3, int(x**0.5)+1, 2):
            while x%d == 0:
                anss.append(d)
                x //= d
        if x != 1:
            anss.append(x)
        return anss

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

    cntP = Counter()
    for A in As:
        PFs = getPrimeFactors(A)
        for key, num in Counter(PFs).items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(maxA, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()

Submission status: Accepted

Solution code:
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class Sieve:
    # Sieve of Eratosthenes
    def __init__(self, n):
        f = [0]*(n+1)
        primes = list()
        f[0] = f[1] = -1
        for i in range(2,n+1):
            if f[i]:
                continue
            primes.append(i)
            f[i]=i
            for j in range(i*i, n+1, i):
                if not f[j]:
                    f[j] = i
        self.f = f
        self.primes = primes
    def isPrime(self, x):
        return self.f[x] == x
    def factorList(self, x):
        res = list()
        while x > 1:
            res.append(self.f[x])
            x //= self.f[x]
        return res
    def factor(self, x):
        fl = self.factorList(x)
        if len(fl) == 0:
            return list()
        res = [[fl[0], 0]]
        for p in fl:
            if res[-1][0] == p:
                res[-1][1] += 1
            else:
                res.append([p, 1])
        return res

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

l = dict()

sv = Sieve(1000005)

for i in range(n):
    f = sv.factor(a[i])
    for p in f:
        try:
            l[p[0]] = max(l[p[0]], p[1])
        except:
            l[p[0]] = p[1]

lcm = mint(1)

for f,s in l.items():
    lcm *= f**s

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
l = 1
mod = 10**9+7
for i in range(n):
  l = lcm(l, a[i])
ans = 0
for i in range(n):
  ans += l // a[i]
print(ans%mod)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
from fractions import gcd
from functools import reduce
def lcm(x,y):
  return (x*y)//gcd(x,y)
mod = 10**9+7
l = reduce(lcm, a) % mod
ans = 0
for i in range(n):
  ans += l * pow(a[i], mod - 2, mod)
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

input = sys.stdin.buffer.readline

LARGE = 10 ** 9 + 7

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

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

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

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

print(total % LARGE)

Submission status: Accepted

Solution code:
import sys
import fractions
input = sys.stdin.buffer.readline
def lcm(x,y):
  return((x*y)//fractions.gcd(x,y))
def main():
  N=int(input())
  arr=list(map(int,input().split()))
  MOD=1000000007 
  LCM=1
  for i in arr:
    LCM=lcm(LCM,i)
  ans=0
  for i in arr:
    ans += LCM//i
  print(ans%MOD)
if __name__=="__main__":
  main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import fractions
from functools import reduce

def main():
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
            
    def lcm(x,y):
        return((x*y)//fractions.gcd(x,y))
        
    l = reduce(lcm,a)
    ans = 0
    for num in a:
        ans += l//num
    
    print(ans%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  from sys import stdin
  from fractions import gcd
  n = int(stdin.readline())
  a = [int(z) for z in stdin.readline().split()]
  lcm = a[0]
  for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
  sm = 0
  for i in range(n):
    sm += lcm // a[i]
  print(sm % (10**9 + 7))

main()

Submission status: Accepted

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

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n = input()
s = list(map(int,input().split()))
L = 1
for i in s:
  L = L * i //gcd(L,i)
ans = 0
for j in s:
  ans += L // j
print(ans % (10**9+7))

Submission status: Accepted

Solution code:
from fractions import gcd

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

LCM = 1

for i in A_List:
    LCM = LCM * i // gcd(LCM, i)

ans = 0

for i in A_List:
    ans += LCM // i

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def lcm_dict(A):
    pf_d=defaultdict(int)
    for num in A:
        for k in range(2,int(num**0.5)+1):
            cnt=0
            while num%k==0:
                cnt+=1
                num//=k
            if cnt:
                pf_d[k]=max(pf_d[k],cnt)
        if num!=1:
            pf_d[num]=max(pf_d[num],1)
    return pf_d

def modinv(k,mod):
    return pow(k,mod-2,mod)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    lcm_d=lcm_dict(A)
    l=1
    for num in lcm_d:
        cnt=lcm_d[num]
        l*=pow(num,cnt,mod)
        l%=mod
    ans=0
    for a in A:
        ans+=l*modinv(a,mod)
        ans%=mod
    print(ans)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)
def modinv(k,mod):
    return pow(k,mod-2,mod)

def main():
    mod=1000000007
    n=int(input())
    A=tuple(map(int,input().split()))
    l=1
    for a in A:
        l=lcm(l,a)
    l%=mod
    ans=0
    for a in A:
        ans+=l*modinv(a,mod)
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
def multi_lcm(array: list) -> dict:
    """arrayのLCMを素因数分解の積の形として求める(ABC152-E)
    入出力例: [4, 18, 21] -> {2: 2, 3: 2, 7: 1}
    key, val = 素因数, 素因数の個数
    """
    pf = {}  # pf: prime_factor
    for num in array:
        for k in range(2, int(num**0.5) + 1):
            cnt = 0
            while num % k == 0:
                cnt += 1
                num //= k
            if cnt != 0:
                if k not in pf:
                    pf[k] = cnt
                else:
                    pf[k] = max(cnt, pf[k])
        if num != 1:
            if num not in pf:
                pf[num] = 1
    return pf

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

factor = multi_lcm(a)
lcm_ = 1
for num in factor:
    cnt = factor[num]
    lcm_ *= pow(num, cnt, MOD)
    lcm_ %= MOD

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

Submission status: Accepted

Solution code:

# from math import gcd
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()))

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

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

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(input().split(), np.int64)
MOD = 10**9+7

U = 10**6 + 10
T = np.zeros(U, np.bool)
T[2] = 1
T[3::2] = 1

for p in range(3,U,2):
  if p*p>U:
    break
  if T[p]==1:
    T[p*p::p+p] = 0

M = np.where(T[:1000])[0].tolist()

B = A.copy()
lcm = 1
for p in M:
  e = 0
  while np.any(A%p==0):
    A[A%p==0] //= p
    e += 1
  lcm *= p**e
  lcm %= MOD
for x in set(A.tolist()):
  lcm *= x
  lcm %= MOD
x = sum(pow(c, MOD-2, MOD) for c in B.tolist())
print(x*lcm%MOD)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(input().split(), np.int64)
MOD = 10**9+7

U = 10**6 + 10
T = np.zeros(U, np.bool)
T[2] = 1
T[3::2] = 1

for p in range(3,U,2):
  if p*p>U:
    break
  if T[p]==1:
    T[p*p::p+p] = 0

pls = np.where(T==1)[0].tolist()
M = pls[:1000]

B = A.copy()
lcm = 1
for p in M:
  e = 0
  while np.any(A%p==0):
    A[A%p==0] //= p
    e += 1
  lcm *= p**e
  lcm %= MOD
for x in set(A.tolist()):
  lcm *= x
  lcm %= MOD
x = sum(pow(c, MOD-2, MOD) for c in B.tolist())
print(x*lcm%MOD)

Submission status: Accepted

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

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

def main():
    n = int(input())
    # a = [int(x) for x in input().split()]
    a = tuple(map(int, input().split()))
    lcm = lcm_list(a)
    aa = []
    for i in range(len(a)):
        aa.append(lcm // a[i])
    ans = sum(aa) % 1000000007
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    lcm = lcm_list(a)
    aa = []
    for i in range(len(a)):
        aa.append(lcm // a[i])
    ans = sum(aa) % 1000000007
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import reduce
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return b // gcd(a, b) * a
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: lcm(x,y), set(a))
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
a = np.array(input().split(), np.int64)
MOD = 10**9+7
U = 10**6+10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
  if p*p>U:
    break
  if is_prime[p]==1:
    is_prime[p*p::p+p] = 0

M = 10**3
small_primes = np.where(is_prime[:M])[0].tolist()

B = a.copy()
lcm = 1
for p in small_primes:
  e = 0
  while np.any(a%p==0):
    a[a%p==0] //= p
    e += 1
  lcm *= p**e
  lcm %= MOD

for x in set(a.tolist()):
  lcm *= x
  lcm %= MOD

answer = sum(pow(x, MOD-2, MOD) for x in B.tolist())%MOD
answer *= lcm
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
from functools import reduce
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return b // gcd(a, b) * a
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: lcm(x,y), a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
x=reduce(lambda x,y: y//gcd(x,y)*x, a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)

Submission status: Accepted

Solution code:
def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)