Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

1 \leq N \leq 10^4

1 \leq A_i \leq 10^6

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 ... A_N

Output

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

Sample Input 1

3
2 3 4

Sample Output 1

13

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

Sample Input 2

5
12 12 12 12 12

Sample Output 2

5

We can let all B_i be 1.

Sample Input 3

3
1000000 999999 999998

Sample Output 3

996989508

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



Sample input:
3
2 3 4


Sample output:
13

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x // gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

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

    ans %= mod

    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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()))
M = 10**9+7
l = 1
for a in A:
    l = lcm(l,a)
ans = 0
for a in A:
    ans += l//a
print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt, floor
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    m = floor(sqrt(n))+1
    for b in range(2,m):
        e = 0
        while n%b == 0:
            n = n // b
            e += 1
        if e > 0:
            fct[b] = e
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t%M
print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from math import sqrt, floor
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    m = floor(sqrt(n))+1
    for b in range(2,m):
        e = 0
        while n%b == 0:
            n = n // b
            e += 1
        if e > 0:
            fct[b] = e
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dct.keys() | dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t%M
print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import functools

MOD = int(1e9) + 7


class Inv:

    @classmethod
    def pow(cls, x: int, n: int) -> int:
        ret = 1
        while n > 0:
            if n % 2 == 1:
                ret = ret * x % MOD
            x = x * x % MOD
            n >>= 1
        return ret

    @classmethod
    def inv(cls, x: int) -> int:
        return cls.pow(x % MOD, MOD - 2)


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

MAX_A = 1000010

facts = [0] * MAX_A

for a in A:
    i = 2
    while i <= a:
        if a % i == 0:
            c1 = 0
            while a % i == 0:
                c1 += 1
                a //= i

            facts[i] = max(facts[i], c1)
        i += 1

tar = 1
for idx, c in enumerate(facts):
    if c == 0:
        continue
    tar *= Inv.pow(idx, c)
    tar %= MOD

ans = 0
for a in A:
    ans += tar * Inv.inv(a) % MOD
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
n,*a=map(int,open(0).read().split())
mod=10**9+7
b=a[0]
for i in a:
    b=b*i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
_,a=open(0)
*a,=map(int,a.split())
mod=10**9+7
b=1
for i in a:
    b*=i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import *
n,*a=map(int,open(0).read().split())
mod=10**9+7
b=1
for i in a:
    b*=i//gcd(b,i)
print(sum(b//i%mod for i in a)%mod)

Submission status: Time Limit Exceeded

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

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

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

t = 1
for i in range(n):
  t = lcm(t, l[i])

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

t = 1
for i in range(n):
  t = lcm(t, l[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
M = 10**9+7
def factorize(n):
    fct = defaultdict(int)
    b, e = 2, 0
    while b*b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct[b] = e
        b, e = b+1, 0
    if n > 1:
        fct[n] = 1
    return fct
dct = defaultdict(int)
dctT = [0]*N
for i,a in enumerate(A):
    dctT[i] = factorize(a)
    for key in dct.keys() | dctT[i].keys():
        dct[key] = max(dct[key],dctT[i][key])
ans = 0
for i in range(N):
    t = 1
    for k,v in dct.items():
        t *= pow(k,v-dctT[i][k],M)
    ans += t
print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(10**6)

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for x in ls:
    counter = factorizations[x]
    s = 1
    for p, k in lcm.items():
        if p in counter:
            k -= counter[p]
        s *= pow(p, k, MOD)
    res += s
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
 
def lcm(a):
	x = a[0]
	for i in range(1, len(a)):
		x = compute_lcm(x, a[i])
	return x

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1 or p > n:
            break
    if n != 1:
        counter[n] = 1
    return counter


sieve = eratosthenes(10**3)
primes = [i for i, b in enumerate(sieve) if b]

MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = []
for x in ls:
    factorizations.append(factorize(x, primes))

lcm = collections.Counter()
for counter in factorizations:
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for counter in factorizations:
    s = 1
    for p, k in lcm.items():
        s *= pow(p, k - counter[p], MOD)
    res += s
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1 or p > n:
            break
    if n != 1:
        counter[n] = 1
    return counter


sieve = eratosthenes(10**3)
primes = [i for i, b in enumerate(sieve) if b]

MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = []
for x in ls:
    factorizations.append(factorize(x, primes))

lcm = collections.Counter()
for counter in factorizations:
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for counter in factorizations:
    s = 1
    for p, k in lcm.items():
        s *= p**(k - counter[p])
        s %= MOD
    res += s
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

t = 0
s = lcm_list(a)
m = 7 + 10**9

for i in range(n):
  t += s // a[i]
  t = t % m 
print(t)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n != 1:
        counter[n] = 1
    return counter


sieve = eratosthenes(10**3)
primes = [i for i, b in enumerate(sieve) if b]

MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = []
for x in ls:
    factorizations.append(factorize(x, primes))
lcm = collections.Counter()
for counter in factorizations:
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for counter in factorizations:
    s = 1
    for p, k in lcm.items():
        s *= p**(k - counter[p])
        s %= MOD
    res += s
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

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())
l = list(map(int, input().split(" ")))

p = lcm_list(l)
c = 0
z = 10 ** 9 + 7
for i in l:
  c += p // i % z
print(c % z)

Submission status: Time Limit Exceeded

Solution code:
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n != 1:
        counter[n] = 1
    return counter


sieve = eratosthenes(10**3)
primes = [i for i, b in enumerate(sieve) if b]

MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = []
for x in ls:
    factorizations.append(factorize(x, primes))
lcm = collections.Counter()
for counter in factorizations:
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for counter in factorizations:
    s = 1
    for p, k in lcm.items():
        s *= p**(k - counter[p])
    res += s
    res %= MOD
print(res)

Submission status: Time Limit Exceeded

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

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

def gcd(a, b):
    while b:
        a, b = b, a%b
    return a
#リストの最小公倍数
def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) #B[0]
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]
    if i % 10 == 0:
        answer %= MOD

print(answer%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class sieve:
  def __init__(self, n):
    self.n = n
    self.sv = [1] * (n + 1)
    self.sv[0] = 0
    self.sv[1] = 0
    for i in range(2, n + 1):
      if self.sv[i]:
        for j in range(i * 2, n + 1, i):
          self.sv[j] = 0
  def isprime(self, x):
    if x > self.n:
      return False
    return self.sv[x] == 1
  def factorize(self, x):
    res = []
    for i in range(2, self.n + 1):
      if self.sv[i]:
        while x % i == 0:
          x //= i
          res.append(i)
    if x != 1:
      res.append(x)
    return res
  def modgcd(self, a, mod):
    res = [float("inf")] * (self.n + 1)
    vis = set()
    f = self.factorize(a[0])
    for j in f:
      res[j] = f.count(j)
      vis.add(j)
    for i in range(1, len(a)):
      f = self.factorize(a[i])
      for j in vis:
        res[j] = min(f.count(j), res[j])
        vis.add(j)
    rres = 1
    for i in range(self.n + 1):
      if res[i] != float("inf"):
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
  def modlcm(self, a, mod):
    res = [0] * (self.n + 1)
    for i in range(len(a)):
      f = self.factorize(a[i])
      for j in f:
        res[j] = max(f.count(j), res[j])
    rres = 1
    for i in range(self.n + 1):
      if res[i] != 0:
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
sv = sieve(10 ** 6)
lcm = sv.modlcm(a, 10 ** 9 + 7)
res = 0
for x in a:
  res += lcm * pow(x, 10 ** 9 + 5, 10 ** 9 + 7)
res %= 10 ** 9 + 7
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class sieve:
  def __init__(self, n):
    self.n = n
    self.sv = [1] * (n + 1)
    self.sv[0] = 0
    self.sv[1] = 0
    for i in range(2, n + 1):
      if self.sv[i]:
        for j in range(i * 2, n + 1, i):
          self.sv[j] = 0
  def isprime(self, x):
    if x > self.n:
      return False
    return self.sv[x] == 1
  def factorize(self, x):
    res = []
    for i in range(2, self.n + 1):
      if self.sv[i]:
        while x % i == 0:
          x //= i
          res.append(i)
    if x != 1:
      res.append(x)
    return res
  def modgcd(self, a, mod):
    res = [float("inf")] * (self.n + 1)
    vis = set()
    f = self.factorize(a[0])
    for j in f:
      res[j] = f.count(j)
      vis.add(j)
    for i in range(1, len(a)):
      f = self.factorize(a[i])
      for j in vis:
        res[j] = min(f.count(j), res[j])
        vis.add(j)
    rres = 1
    for i in range(self.n + 1):
      if res[i] != float("inf"):
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
  def modlcm(self, a, mod):
    res = [0] * (self.n + 1)
    for i in range(len(a)):
      f = self.factorize(a[i])
      for j in f:
        res[j] = max(f.count(j), res[j])
    rres = 1
    for i in range(self.n + 1):
      if res[i] != 0:
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
sv = sieve(10 ** 6)
lcm = sv.modlcm(a, 10 ** 9 + 7)
res = 0
for x in a:
  res += lcm * pow(x, 10 ** 9 + 5, 10 ** 9 + 7)
  res %= 10 ** 9 + 7
print(res)

Submission status: Time Limit Exceeded

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

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

import fractions
#from functools import reduce
def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

ans = 0
cl = 1
for i in range(n):
  x = l[i]
  y = lcm_base(cl, l[i])
  ans *= y//cl
  ans += y//x
  ans %= (10**9+7)
  cl = y
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = lcm * T[i] // fractions.gcd(lcm, T[i])
for x in T:
  ans = (ans + lcm // x) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
MOD = 1000000007  # type: int


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(N: int, A: "List[int]"):

    primes = eratosthenes_sieve(max(A)+1)

    def factorial(n):
        # 試し割りによる素因数分解
        prime_count = Counter()
        for i in primes:
            while n % i == 0:
                n /= i
                prime_count[i] += 1
        if n > 1:
            prime_count[int(n)] += 1
        return prime_count

    C = [factorial(a) for a in A]

    K = Counter()
    for c in C:
        for k in c:
            K[k] = max(K[k], c[k])

    tot = 0
    for i in range(N):
        a = 1
        for k in K:
            if K[k] - C[i][k] != 0:
                a *= k**(K[k] - C[i][k])
                a %= MOD
        tot += a
        tot %= MOD
    print(tot)

    return


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

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
MOD = 1000000007  # type: int


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(N: int, A: "List[int]"):

    primes = eratosthenes_sieve(10**3)

    def factorial(n):
        # 試し割りによる素因数分解
        prime_count = Counter()
        for i in primes:
            while n % i == 0:
                n /= i
                prime_count[i] += 1
        if n > 1:
            prime_count[int(n)] += 1
        return prime_count

    C = [factorial(a) for a in A]

    K = Counter()
    for c in C:
        for k in c:
            K[k] = max(K[k], c[k])

    B = [0]*N
    for i in range(N):
        b = Counter()
        for k in K:
            b[k] = K[k] - C[i][k]
        a = 1
        for k in b:
            if b[k] != 0:
                a *= k**b[k]
                a %= MOD
        B[i] = a
    print(sum(B) % MOD)

    return


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

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

N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = (lcm * T[i]) // gcd(lcm, T[i])
for i in range(N):
  ans = (ans + lcm // T[i]) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = lcm * T[i] // fractions.gcd(lcm, T[i])
for i in range(N):
  ans = (ans + lcm//T[i]) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

amari = 10**9+7

a = A[0]
for i in range(1, N):
    a = a * A[i] // fractions.gcd(a, A[i])

ans = 0
for i in range(N):
    ans %= amari
    ans += a//A[i]

print(ans%amari)

Submission status: Time Limit Exceeded

Solution code:
hell=1000000007

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
# This function computes LCM
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
   
n=int(input())
a=[int(i) for i in input().split()]
l=1

for i in set(a):
	l=compute_lcm(l,int(i))
b=0

for i in a:
	b+=(l//i)
	b=b%hell
	# 996989508
print(b%hell)

Submission status: Time Limit Exceeded

Solution code:
hell=1000000007

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
# This function computes LCM
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
   
n=int(input())
a=[int(i) for i in input().split()]
l=1
for i in a:
	l=compute_lcm(l,int(i))
b=0

for i in a:
	b+=(l//i)
	b=b%hell
	# 996989508
print(b%hell)

Submission status: Time Limit Exceeded

Solution code:
def inv(x):
    return pow(x, MOD-2, MOD)


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

primes = {}

for val in A:
    p = 2
    while val >= p * p:
        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

lcm = 1
for p in primes:
    lcm *= p ** primes[p]
    lcm %= MOD
# print(lcm)
ans = 0

for val in A:
    ans += lcm * inv(val)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

n, *a = map(int, open(0).read().split())

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

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

lcm = lcm_list(a)

ans = 0
for a_i in a:
  ans += lcm // a_i

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
lcm = dict()
mod = 10**9+7
for a in A:
    n = 2
    while a != 1:
        c = 0
        while a % n == 0:
            a //= n
            c += 1
        if not n in lcm:
            lcm[n] = 0
        lcm[n] = max(lcm[n], c)
        n += 1
l = 1
for n in lcm.keys():
    l *= pow(n, lcm[n], mod)
l %= mod
ans = 0
for a in A:
    p = pow(a, mod-2, mod)
    ans += (l*p)
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from math import sqrt

MOD = 10**9+7
p_list = {}  # 最大公約数を素因数分解したもの

def prime_decomposition(n):
    i = 2
    a = []
    while i <= int(sqrt(n))+1:
        while n % i == 0:
            n //= i
            a.append(i)
        i += 1
    if n > 1:
        a.append(n)
    return a


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

    for i in a:
        l = Counter(prime_decomposition(i))
        for k, v in l.items():
            if p_list.get(k):
                p_list[k] = max(p_list[k], v)
            else:
                p_list[k] = v

    # ここからMODを法として考える
    lcm = 1
    for k, v in p_list.items():
        lcm *= pow(k, v, MOD)
        lcm %= MOD

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
MOD = 10**9+7

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

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    a = v[0]
    lcm = v[0]
    for i in range(n):
        if i > 0:
            tmp = a
            a = gcd(a, v[i])
            c_lcm = tmp * v[i] // a
            lcm = c_lcm * lcm // gcd(c_lcm, lcm)
    ans = 0
    for i in range(n):
        ans += lcm // v[i] % MOD
    print(ans % MOD)
    # for i in range(n):
    #     ans += lcm * pow(v[i], MOD-2, MOD)
    # print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
P = 10**9 + 7
N = 1000001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
for i in range(2,N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
lcm=[0]*(max(a)+2)
for i in range(n):
  k=a[i]
  for j in range(1,int(a[i]**0.5)+1):
    cnt=0
    while k%(j+1)==0:
      k//=j+1
      cnt+=1
    lcm[j+1]=max(cnt,lcm[j+1])
  lcm[k]=max(1,lcm[k])
lcmn=1
for i in range(len(lcm)):
  if lcm[i]>0:
    lcmn*=i**lcm[i]%mod
lcmn%=mod
ans=0
for i in range(n):
  ans+=lcmn*inv[a[i]]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

def primeList(N):
    R = int(N**0.5) + 10
    isPrime = [True] * (R + 1)
    for p in range(2, R):
        if not isPrime[p]:
            continue
        for q in range(p * 2, R, p):
            isPrime[q] = False
    return {p for p in range(2, R) if isPrime[p]}

primes = primeList(max(A))

def primeCount(N):
    ret = defaultdict(int)  # 素数のリスト
    n = N
    for num in primes:
        ret[num] = 0
        while n % num == 0:
            n //= num
            ret[num] += 1
    if n > 1 :
        ret[n] = 1
    return ret

PC = [primeCount(a) for a in A]
L = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        L[p] = max(L[p], c)

ans = 0
for pc in PC:
    b = 1
    for p, c in L.items():
        b *= pow(p, c - pc[p], MOD)
        b %= MOD
    ans += b
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd

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

    MOD = 10 ** 9 + 7

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

    ans = 0
    for a in A:
        ans += tmp // a
        ans %= MOD

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

MOD = 10 ** 9 + 7

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

ans = 0
for a in A:
    ans += tmp // a
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np
def lcm(h, g):
    return (h * g) // fractions.gcd(h, g)
N = int(input())
A = list(map(int,input().split()))
cnt = 1
ans = 0
for i in range(N):
    cnt = lcm(cnt, A[i])
for i in range(N):
    ans += (cnt//A[i])
print((ans)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

import math

def factoring(k): #kを因数分解し、素因数とその個数を辞書に入れて返す。
    dic = dict()
    n = int(math.sqrt(k))+2
    for i in range(2, n):
        count = 0
        while k%i == 0:
            count += 1
            k = k//i
        if count != 0:
            dic[i] = count
    if k != 1: #sqrt(k)までチェックしてもkが1になっていない --> kが素因数
        dic[k] = 1
    return dic


lst = [0] * (10 ** 6 + 1)
for a in A:
    dic = factoring(a)
    for d in dic:
        lst[d] = max(lst[d], dic[d])

tmp = 1
for index, x in enumerate(lst):
    tmp *= index ** x

# print (tmp)

ans = 0
for a in A:
    ans += tmp // a
    ans %= MOD

print (ans)

Submission status: Time Limit Exceeded

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

is_prime = np.zeros(U,np.bool) #素数列挙(エラトステネス)
is_prime[2] = 1
is_prime[3::2] = 1
# print(is_prime)
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

# M = 10**3
# small_primes = np.where(is_prime[:M])[0].tolist()
small_primes = is_prime.tolist()
B = A.copy()
lcm = 1
for p in small_primes:
    e = 0
    while np.any(A % p == 0):
        e += 1
        A[A%p == 0] //= p
    lcm *= p**e
    lcm %= MOD


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