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:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import copy
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = 10**9 + 7


def fact(N):
    res = {}
    tmp = N
    for i in range(2, int(N ** 0.5 + 1) + 1):
        cnt = 0
        while tmp % i == 0:
            cnt += 1
            tmp //= i
        if cnt > 0:
            res[i] = cnt
    if tmp != 1:
        res[tmp] = 1
    if res == {}:
        res[N] = 1
    return res


def modpow(n, p):
    res = 1
    while p > 0:
        if p & 1:
            res = res * n % MOD
        n = n * n % MOD
        p >>= 1
    return res


def sub(a, b):
    for k, v in b.items():
        a[k] -= v
    res = 1
    for k, v in a.items():
        if v == 0:
            continue
        res *= modpow(k, v)
        res %= MOD
    for k, v in b.items():
        a[k] += v
    return res


def solve():
    N = Scanner.int()
    A = Scanner.map_int()
    L = defaultdict(int)
    facts = [{} for _ in range(N)]
    for i in range(N):
        facts[i] = fact(A[i])
    for i in range(N):
        for k, v in facts[i].items():
            L[k] = max(L[k], v)
    ans = 0
    for i in range(N):
        x = sub(L, facts[i])
        ans += x
        ans %= MOD
    print(ans)


def main():
    # sys.setrecursionlimit(1000000)
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

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

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

    LCM = lcm(*A)
    MOD = 10 ** 9 + 7
    ans = 0
    for i in range(N):
        ans = (ans + LCM // A[i]) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

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

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

LCM = lcm(*A)
MOD = 10 ** 9 + 7
ans = 0
for i in range(N):
    ans = (ans + LCM // A[i]) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    ans = 0
    l = 1
    for p, n in L.items():
        l = l * pow(p, n, MOD) % MOD

    for i, a in enumerate(A):
        ans += l * pow(a, -1, MOD) % MOD
    print(ans % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        for p, n in L.items():
            primes_a[a].setdefault(p, 0)
            b = b * pow(p, (n - primes_a[a][p]), MOD) % MOD
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        for p, n in L.items():
            primes_a[a].setdefault(p, 0)
            b *= pow(p, (n - primes_a[a][p]), MOD)
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        for j in range(root+1):
            if n % i == 0 and n != 0:
                cnt += 1
                n = n // i
            else:
                break
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        for p, n in L.items():
            primes_a[a].setdefault(p, 0)
            b *= p ** (n - primes_a[a][p])
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    primes_a = {}
    for a in A:
        prime_a = prime_fact(a)
        primes_a[a] = prime_a
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        for p, n in L.items():
            primes_a[a].setdefault(p, 0)
            b *= p ** (n - primes_a[a][p])
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# Nの素因数分解を辞書で返す
def prime_fact(n):
    root = int(math.sqrt(n))
    prime_dict = {}
    for i in range(2, root+1):
        cnt = 0
        while n % i == 0:
            cnt += 1
            n = n // i
        if cnt:
            prime_dict[i] = cnt
    if n != 1:
        prime_dict[n] = 1
    return prime_dict


def main():
    N = NI()
    A = NLI()
    L = {}
    B = [0] * N
    for a in A:
        prime_a = prime_fact(a)
        for p, n in prime_a.items():
            L.setdefault(p, 0)
            L[p] = max(L[p], n)
    for i, a in enumerate(A):
        b = 1
        prime_a = prime_fact(a)
        for p, n in L.items():
            prime_a.setdefault(p, 0)
            b *= p ** (n - prime_a[p])
        B[i] = b
    print(sum(B) % MOD)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_primes(n):
    assert n >= 2
    is_prime = [False if i % 2 == 0 else True for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = True
    for i in range(3, n + 1, 2):
        if i ** 2 >= n:
            break
        for j in range(2 * i, n + 1, i):
            is_prime[j] = False
    return [i for i, b in enumerate(is_prime) if b == True]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes(max(max(A), 3))
    prime_indices = {p: i for i, p in enumerate(primes)}
    lcm_pf = [0 for _ in range(len(primes))]
    a_pf = [[0 for _ in range(len(primes))] for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
            if p ** 2 > a:
                # 'a' is a prime
                a_pf[i][prime_indices[a]] += 1
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_primes(n=10**6):
    primes = [2]
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return primes + data
        primes.append(p)
        data = [d for d in data if d % p != 0]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes(max(max(A), 3))
    lcm_pf = [0] * len(primes)
    a_pf = [[0] * len(primes) for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_primes(n=10**6):
    primes = [2]
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if n <= p ** 2:
            return primes + data
        primes.append(p)
        data = [d for d in data if d % p != 0]


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    A = list(map(int, input().split(' ')))
    # 答えは sum(lcm(A) / A)
    primes = get_primes()
    lcm_pf = [0] * len(primes)
    a_pf = [[0] * len(primes) for _ in range(N)]
    # lcm(A) の素因数分解表示を計算
    for i, a in enumerate(A):
        for j, p in enumerate(primes):
            while a % p == 0:
                a_pf[i][j] += 1
                a //= p
            if a == 1:
                break
        for j in range(len(primes)):
            lcm_pf[j] = max(lcm_pf[j], a_pf[i][j])
    # sum(lcm(A) / A) を計算
    ans = 0
    for i in range(N):
        v = 1
        for j, p in enumerate(primes):
            e = lcm_pf[j] - a_pf[i][j]
            v *= p ** e
            v %= MOD
        ans += v
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
def f(x):
  if x==1:
    return dict()
  y=x
  r=dict()
  for i in range(2,int(x**0.5)+1):
    if y%i==0:
      r[i]=0
      while y%i==0:
        r[i]+=1
        y=y//i
    if y==1:
      break
  if y!=1:
    r[y]=1
  return r

B=[f(A[i]) for i in range(N)]
G=dict()
def g(x,y):
  z=list(set(x.keys())|set(y.keys()))
  r=dict()
  for i in range(len(z)):
    r[z[i]]=max(x.get(z[i],0),y.get(z[i],0))
  return r

for i in range(N):
  G=g(G,B[i])
X=1
mod=10**9+7
P=0
Y=list(G.keys())
for i in range(len(Y)):
  X=X*pow(Y[i],G[Y[i]],mod)%mod
for i in range(N):
  P=(P+X*pow(A[i],mod-2,mod))%mod
print(P)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y

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

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

def addmod(a, b):
    return (a+b) % MOD
  
  
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7

l = reduce(lcm, a_list)
ans = reduce(addmod, (l//a for a in a_list))

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y
 
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7
 
if N == 1:
    print(1)
    exit()
div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) // div
 
for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) // div
    
ans = 0
for i in range(N):
    ans += lcm//a_list[i] % MOD
 
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x, y):
    if x < y:
        x, y = y, x
    while x % y != 0:
        r = x % y
        x = y
        y = r
    return y
 
N = int(input())
a_list = list(map(int, input().split()))
MOD = 10 ** 9 + 7
 
if N == 1:
    print(1)
    exit()
div = gcd(a_list[0], a_list[1])
lcm = (a_list[0] * a_list[1]) // div
 
for i in range(2, N):
    div = gcd(lcm, a_list[i])
    lcm = (lcm * a_list[i]) // div
    
ans = 0
for i in range(N):
    ans = (ans + lcm//a_list[i]) % MOD
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
prime_list = defaultdict(int)

def prime_factorize(n):
    divisors = []
    # 27(2 * 2 * 7)の7を出すためにtemp使う
    temp = n
    for i in range(2, int(math.sqrt(n)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                # 素因数を見つけるたびにtempを割っていく
                temp //= i
            divisors.append([i, cnt])
    if temp != 1:
        divisors.append([temp, 1])
    if divisors == []:
        divisors.append([n, 1])

    return divisors

for i in range(N):
    prime = prime_factorize(A[i])
    for j in prime:
        prime_list[j[0]] = max(prime_list[j[0]], j[1])

ans = 0
for i in range(N):
    opt = 1
    list_alta = copy.deepcopy(prime_list)
    prime = prime_factorize(A[i])
    for j in prime:
        list_alta[j[0]] -= j[1]
    for key, value in list_alta.items():
        opt *= key ** value
        opt %= mod
    ans += opt
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce

N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 + 7

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    prime = [0] * max(A)
    for a in A:
        primes = prime_factorization(a)
        for num, ex in primes:
            prime[num - 1] = max(prime[num - 1], ex)

    L = 1
    for i in range(len(prime)):
        if prime[i] == 0:
            continue
        L *= pow(i + 1, prime[i])

    res = 0
    for a in A:
        res += L // a
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import gcd

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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


def resolve():
    n = int(input())
    A = list(map(int, input().split()))

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

    res = 0
    for a in A:
        res += L // a
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


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

    P = [0] * N
    P_max = defaultdict(int)
    for i in range(N):
        P[i] = Counter(prime_factorize(A[i]))
        for p, n in P[i].items():
            if P_max[p] < n:
                P_max[p] = n

    ans = 0
    for i in range(N):
        P_i = P[i]
        b = 1
        for p, n in P_max.items():
            b = b * pow(p, n - P_i[p], MOD) % MOD
        ans = (ans + b) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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


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

    l = reduce(lcm, A)

    ans = 0
    for a in A:
        ans = (ans + l // a) % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

MOD = 10 ** 9 + 7

_ = int(input())
la = 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)


def addmod(a, b):
    return (a + b) % MOD


l = reduce(lcm, la)
answer = reduce(addmod, (l // a for a in la))
print(answer)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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


def prime_factorization(n):
    pmax = int(n ** 0.5 // 1) + 1

    factors = {}
    for p in range(2, pmax + 1):
        while n % p == 0:
            factors[p] = factors.get(p, 0) + 1
            n //= p
    if n != 1:
        factors[n] = factors.get(n, 0) + 1

    return factors

lf = [prime_factorization(a) for a in la]


lcm_factors = {}

for factors in lf:
    for p, m in factors.items():
        lcm_factors[p] = max(lcm_factors.get(p, 0), m)

s = 0
for factors in lf:
    b = 1
    for p, m in lcm_factors.items():
        b *= p ** (m - factors.get(p, 0))
        b %= MOD
    s += b
    s %= MOD

print(s)

Submission status: Time Limit Exceeded

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

big = 10 ** 9 + 7

N = int(input())
A = list(map(int, input().split()))
num = A[0]
for i in range(1, N):
    num = num * A[i] // math.gcd(num, A[i])

res = 0
for a in A:
    res += num // a % big

print(res % big)

Submission status: Time Limit Exceeded

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

import math

big = 10**9 + 7

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

A = []
for a in row_A:
    A.append(a%big)


num = A[0]
set_A = set(A)

for a in set_A:
    num = num * a // math.gcd(num, a)

res = 0
for a in A:
    res += num//a % big

print(res%big)

Submission status: Time Limit Exceeded

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

import math

big = 10**9 + 7

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

A = []
for a in row_A:
    A.append(a%big)


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

res = 0
for a in A:
    res += num//a % big

print(res%big)

Submission status: Time Limit Exceeded

Solution code:
import math

big = 10**9 + 7

N = int(input())
A = list(map(int, input().split()))
num = A[0]
for i in range(1, N):
    num = num * A[i] // math.gcd(num, A[i])

res = 0
for a in A:
    res += num//a % big

print(res%big)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy


mod = 10 ** 9 + 7
primes = []
for i in range(2,1002):
  for prime in primes:
    if not i % prime:
      break
  else:
    primes.append(i)

def factorize(n):
  now = n
  fct = defaultdict(int)
  for prime in primes:
    cnt = 0
    if prime ** 2 > n:
      break
    while not now % prime:
      now //= prime
      cnt += 1
    if cnt:
      fct[prime] = cnt
  if now > 1:
    fct[now] = 1
  return fct


n = int(input())
a = list(map(int, input().split()))
fct_a = list()
for i in a:
  fct_a.append(factorize(i))
lcm = defaultdict(int)
for i in fct_a:
  for k,v in i.items():
    lcm[k] = max(lcm[k], v)
ans = 0
for i in fct_a:
  b = 1
  for k,v in lcm.items():
    b *= k**(v-i[k])
    b %= mod
  ans += b
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy


mod = 10 ** 9 + 7
primes = []
for i in range(2,1002):
  for prime in primes:
    if not i % prime:
      break
  else:
    primes.append(i)

def factorize(n):
  now = n
  fct = defaultdict(int)
  for prime in primes:
    cnt = 0
    if prime ** 2 > n:
      break
    while not now % prime:
      now //= prime
      cnt += 1
    if cnt:
      fct[prime] = cnt
  if now > 1:
    fct[now] = 1
  return fct


n = int(input())
a = list(map(int, input().split()))
fct_a = list()
for i in a:
  fct_a.append(factorize(i))
lcm = defaultdict(int)
for i in fct_a:
  for k,v in i.items():
    lcm[k] = max(lcm[k], v)
ans = 0
for i in fct_a:
  b = 1
  for k,v in lcm.items():
    b *= pow(k,v-i[k])
    b %= mod
  ans += b
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import copy


mod = 10 ** 9 + 7
primes = []
for i in range(2,1002):
  for prime in primes:
    if not i % prime:
      break
  else:
    primes.append(i)

def factorize(n):
  now = n
  fct = dict()
  for prime in primes:
    cnt = 0
    if prime ** 2 > n:
      break
    while not now % prime:
      now //= prime
      cnt += 1
    if cnt:
      fct[prime] = cnt
  if now > 1:
    fct[now] = 1
  return fct


n = int(input())
a = list(map(int, input().split()))
fct_a = list()
for i in a:
  fct_a.append(factorize(i))
lcm = defaultdict(int)
for i in fct_a:
  for k,v in i.items():
    lcm[k] = max(lcm[k], v)
ans = 0
for i in fct_a:
  bi = copy.copy(lcm)
  for k,v in i.items():
    bi[k] -= v
  b = 1
  for k,v in bi.items():
    b *= k ** v
    b %= mod
  ans += b
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# import bisect
# from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    MOD=10**9+7
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )
    
    n=int(input())
    A=list(map(int,input().split()))

    from functools import reduce
    from math import gcd
    
    def lcm(A, B):
        return A * B // gcd(A, B)
    
    
    # リストを引数にとる
    val=reduce(lcm, A)
    ans=ModInt(0)
    for i in A:
        ans+=val//i
    print(ans)
    


    
resolve()