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:
from collections import defaultdict

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

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in A]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        if c > primes[p]:
            primes[p] = c

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

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 primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = defaultdict(int)  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return primes

PC = [primeCount(a) for a in A]

primes = defaultdict(int)
for pc in PC:
    for p, c in pc.items():
        primes[p] = max(primes[p], c)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n=int(input())
mod=1000000007
sum=0
s=[int(n) for n in input().split()]
ans=1
for i in s:
    ans*=i//fractions.gcd(ans,i)
for i in s:
    sum=(sum+ans//i)%mod
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 10**9 + 7
n = int(input())
lst = list(map(int, input().split()))
koubai = lst[0]
def gcd(a, b):
    if a > b:
        a, b = b, a
    while b > 0:
        a, b = b, a % b
    return a
for i in range(1, n):
    koubai = koubai*lst[i]//gcd(koubai, lst[i])
 
total = 0
for l in lst:
    b = koubai//l
    total += b
    total %= mod
print(total)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm=1
d=dict()
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]
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
    if j+1 in d:
      if d[j+1]<cnt:
        lcm*=(j+1)**(cnt-d[j+1])%mod
        d[j+1]=cnt
    else:
      lcm*=(j+1)**cnt%mod
      d[j+1]=cnt
  if k in d:
    if d[k]<1:
      lcm*=k
      d[k]=1
  else:
    lcm*=k
    d[k]=1
ans=0
lcm%=mod
for i in range(n):
  ans+=lcm*inv[a[i]]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm=1
d=dict()
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
    if j+1 in d:
      if d[j+1]<cnt:
        lcm*=(j+1)**(cnt-d[j+1])
        d[j+1]=cnt
    else:
      lcm*=(j+1)**cnt
      d[j+1]=cnt
  if k in d:
    if d[k]<1:
      lcm*=k
      d[k]=1
  else:
    lcm*=k
    d[k]=1
ans=0
for i in range(n):
  ans+=(lcm//a[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
lcm=1
d=dict()
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
    if j+1 in d:
      if d[j+1]<cnt:
        lcm*=(j+1)**(cnt-d[j+1])
        d[j+1]=cnt
    else:
      lcm*=(j+1)**cnt
      d[j+1]=cnt
  if k in d:
    if d[k]<1:
      lcm*=k
      d[k]=1
  else:
    lcm*=k
    d[k]=1
ans=0
for i in range(n):
  ans+=(lcm//a[i])%mod
print(ans%mod)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
lcm = lambda x, y: (x*y)//gcd(x,y)
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
l = reduce(lcm, a)
ans = 0
for x in a:
    ans += l//x
print(ans%MOD)

Submission status: Time Limit Exceeded

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

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

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

L = A[0]
for a in set(A):
    L = lcm(L, a)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
from math import sqrt

MOD = 10**9+7
p_list = defaultdict(int)

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


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():
            p_list[k] = max(p_list[k], v)
    
    lcm = 1
    for k, v in p_list.items():
        lcm *= int(k)**v

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

    print(int(ans) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(i,j):
  if i == 0: return j
  if j == 0: return i
  return i*j // gcd(i,j)

MOD = 10**9+7
n = int(input())
a = list(map(int,input().split()))
k = 0
for i in range(n):
  k = lcm(k,a[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

def lcm(i,j):
  if i == 0: return j
  if j == 0: return i
  return i*j // gcd(i,j)

MOD = 10**9+7
n = int(input())
a = list(map(int,input().split()))
k = 0
for i in range(n):
  k = lcm(k,a[i])

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

'''
lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)
'''

from functools import reduce

lcm=reduce(lambda x,y :(x*y)//gcd(x,y),a)
ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from collections import deque
import numpy as np
import heapq
import math
import fractions
from heapq import heappush, heappop


#read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


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


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

lm = 1
s = 0

for i in range(N):
    lm = lcm(A[i], lm)
    #s += lm // MOD
    #lm %= MOD

#lm %= MOD
# print(lm)
ans = 0
for i in range(N):
    m = modinv(A[i], MOD)
    ans += lm * m
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lcm=1
for i in a:
 lcm=(lcm*i)//gcd(lcm,i)

ans=0
mod=10**9+7
for i in a:
 ans+=lcm//i
 ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#pypyでreduceは速いのか?

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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

lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
ans=0
for i in range(N):
    ans+=lcm//A[i]
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**6+1)

d = defaultdict(lambda : 0)

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if c > d[p]:
            d[p] = c
    if elt > 1 and d[elt] == 0:
        d[elt] = 1



lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

res = 0
for e in a:
    res = (res + pow(e,mod-2,mod))%mod
print(res*lcm%mod)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a)
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
    ans %= MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
MOD = 10**9 + 7
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

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

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

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

num = lcm_list(a)
ans = 0
for i in a:
    ans += num // i
    ans %= MOD
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def e_flatten_prime_factorization(MOD=10**9 + 7):
    N = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        from collections import defaultdict
        """nを素因数分解したときの素数とその指数の辞書"""
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    def prime_table(n):
        """n以下の素数のリスト(エラトステネスの篩)"""
        is_prime = [True] * (n + 1)
        is_prime[0] = is_prime[1] = False  # 0と1は素数でない
        for j in range(2, int(n**0.5) + 1):
            if not is_prime[j]:
                continue
            for k in range(j * 2, n + 1, j):
                is_prime[k] = False  # jの倍数は素数でない
        return {i: 0 for i in range(n + 1) if is_prime[i]}

    lcm_prime = prime_table(10**6)
    for a in A:
        for base, exp in prime_factorization_dict(a).items():
            lcm_prime[base] = max(lcm_prime[base], exp)
    lcm = 1
    for base, exp in lcm_prime.items():
        lcm *= pow(base, exp, MOD)
        lcm %= MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten_prime_factorization())

Submission status: Time Limit Exceeded

Solution code:
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**6+1)

d = dict()

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if p in d:
            if c > d[p]:d[p] = c
        elif c != 0:
            d[p] = c


lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

res = 0
for e in a:
    res = (res + pow(e,mod-2,mod))%mod
print(res*lcm%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

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

ans = 0
for a in A:
    ans += t//a%mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

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

n=max(A)+5

#is_prime[i]にはi-1画素数か否かを示すboolが入る，[0]に1の素数判定がある．
is_prime = [True]*(n+1)
is_prime[0] = False

for i in range(2, n+1):
    if is_prime[i-1]:
        j = 2 * i
        while j <= n:
            is_prime[j-1] = False
            j += i

table = [ i for i in range(1, n+1) if is_prime[i-1]]
#print(table)


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

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

Submission status: Time Limit Exceeded

Solution code:
#n以下の素数列挙(O(n log(n))
def primes(n):
    ass = []
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.append(i)
    return ass


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

pr = primes(10**6+1)

d = dict()

for elt in a:
    for p in pr:
        if elt < p:
            break
        c = 0
        while not elt%p:
            c += 1
            elt //= p
        if p in d:
            if c > d[p]:d[p] = c
        else:
            d[p] = c


lcm  = 1
for elt in d:
    lcm = lcm*pow(elt,d[elt],mod)%mod

res = 0
for e in a:
    res = (res + pow(e,mod-2,mod))%mod
print(res*lcm%mod)

Submission status: Time Limit Exceeded

Solution code:
def e_flatten_prime_factorization(MOD=10**9 + 7):
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        """nを素因数分解したときの素数とその指数の辞書"""
        from collections import defaultdict
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, defaultdict(int)
        while i**2 <= n:
            while n % i == 0:
                table[i] += 1
                n //= i
            i += 1
        if n > 1:
            table[n] = 1
        return table

    lcm_prime = defaultdict(int)
    for a in A:
        for base, exp in prime_factorization_dict(a).items():
            lcm_prime[base] = max(lcm_prime[base], exp)
    lcm = 1
    for base, exp in lcm_prime.items():
        lcm *= pow(base, exp, MOD)
        lcm %= MOD
    coefficient = sum(pow(a, MOD - 2, MOD) for a in A)
    return (lcm * coefficient) % MOD

print(e_flatten_prime_factorization())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# from functools import reduce
# from math import gcd as gcd_base  # from fractions import gcd
# gcd = lambda *numbers: reduce(gcd_base, numbers)  # 3 数以上の最大公約数

# lcm_base = lambda x, y: (x * y) // gcd_base(x, y)
# lcm = lambda *numbers: reduce(lcm_base, numbers, 1)  # 3 数以上の最小公倍数
# 最小公倍数
# def gcd(a, b):
#     if a < b:
#         a, b = b, a
#     while a % b != 0:
#         a, b = b, a % b
#     return b


## 最大公約数 
def lcm(a, b):
    y = a*b // gcd(a, b)
    return y

def many_lcm(l):
    tmp = l[0]
    for i in range(1, len(l)):
        tmp = lcm(tmp, l[i])
    return tmp
N = INT()
A = LIST()

lm = many_lcm(A)
# print(l)
B = []
for a in A:
    B.append(lm // a)
print(sum(B) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from fractions import gcd
from functools import reduce
 
N,*A = map(int,read().split())
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum((lcm//x) % MOD for x in A)
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce
 
N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum((lcm//x) % MOD for x in A)
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


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


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


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

res = 0
for i, a in enumerate(A):
    res = (res + (_lcm * pow(A[i], MOD - 2, MOD))) % MOD

print(res)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7


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


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


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

res = 0
for i, a in enumerate(A):
    res = (res + (_lcm * pow(A[i], MOD - 2, MOD))) % MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
 
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*y//gcd(x,y), A)
 
answer = sum(lcm//x for x in A)
answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
 
MOD = 10**9 + 7
 
from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)
 
x = lcmm(A)
 
ans = sum(x//a for a in A)
ans %= MOD
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


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


N = int(input())
A = list(map(int, input().split()))
_lcm = 1
for a in A:
    _lcm = lcm(_lcm, a)
ans = 0
for a in A:
    ans += _lcm // a
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr

def main():
    N=int(input())
    A=[int(i) for i in input().split()]
    MOD=1000000007
    lcm = 1
    gcd=fr.gcd
    for i in range(N):
        lcm = A[i] * lcm //gcd(A[i], lcm)

    sumval=0
    for i in range(N):
        sumval = (sumval+lcm//A[i])

    print(sumval%MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr

def main():
    N=int(input())
    A=[int(i) for i in input().split()]
    MOD=1000000007
    lcm = 1
    for i in range(N):
        lcm = A[i] * lcm //fr.gcd(A[i], lcm)

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

    print(sumval)


main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

def factorize(n):
    res = defaultdict(int)
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            res[d] += 1
        d += 1
    if n > 1:
        res[n] += 1
    return res

factors = [factorize(val) for val in a]
lcm = defaultdict(int)
for d in factors:
    for num in d.keys():
        lcm[num] = max(lcm[num], d[num])

ret = 0
for i, d in enumerate(factors):
    val = 1
    for num in lcm.keys():
        val *= pow(num, lcm[num] - d[num], MOD)
        val %= MOD
    ret += val
    ret %= MOD
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

def factorize(n):
    res = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            res.append(d)
        d += 1
    if n > 1:
        res.append(n)
    return res

factors = []
for val in a:
    d = defaultdict(int)
    for factor in factorize(val):
        d[factor] += 1
    factors.append(d)
lcm = defaultdict(int)
for d in factors:
    for num, cnt in d.items():
        lcm[num] = max(lcm[num], cnt)

ret = 0
for i, d in enumerate(factors):
    val = 1
    for num, cnt in lcm.items():
        val *= max(1, num ** (cnt - d[num]))
    ret += val
    ret %= MOD
print(ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 10 ** 9 + 7

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

def factorize(n):
    res = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            res.append(d)
        d += 1
    if n > 1:
        res.append(n)
    return res

factors = []
for val in a:
    d = defaultdict(int)
    for factor in factorize(val):
        d[factor] += 1
    factors.append(d)
lcm = defaultdict(int)
for d in factors:
    for num, cnt in d.items():
        lcm[num] = max(lcm[num], cnt)

ret = 0
for i, d in enumerate(factors):
    val = 1
    for num, cnt in lcm.items():
        val *= pow(num, cnt - d[num], MOD)
        val %= MOD
    ret += val
    ret %= MOD
print(ret)

Submission status: Time Limit Exceeded

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

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

def lcm(x, y):
    return x/gcd(x, y)*y
 
l = A[0]
for a in A:
    l = lcm(l, a)
 
res = 0

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

print(res)

Submission status: Time Limit Exceeded

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

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

def lcm(x, y):
    return x/gcd(x, y)*y
 
l = A[0]
for a in A:
    l = lcm(l, a)
 
res = 0

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
N = int(input())
A = [int(i) for i in input().split()]
ans = 1
cur_lcm = A[0]
mod = 10**9 +7
for i in range(N):
    if i == 0:
        continue
    else:
        temp_lcm = cur_lcm*A[i]//fractions.gcd(cur_lcm,A[i])
        if temp_lcm == cur_lcm:
            ans +=  temp_lcm//A[i]
        else:
            ans *= temp_lcm//cur_lcm
            ans += temp_lcm//A[i]
            cur_lcm = temp_lcm
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

lcm1 = 1

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

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

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

ans = 0

for i in a:
    ans += lcm1 // i

print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  if a%i==0:
    continue
  a = lcm(a,i)
ans = 0
A =np.array(A)
ans = np.sum(a//A)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import numpy as np
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
A =np.array(A)
ans = np.sum(a//A)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

factors = {}
for a in A:
    for i in range(2, int(a**0.5)+1):
        cnt = 0
        while a % i == 0:
            cnt += 1
            if i in factors:
                factors[i] = max(factors[i], cnt)
            else:
                factors[i] = cnt
            a //= i
    if a != 1 and a not in factors:
        factors[a] = 1

l = 1
for k, v in factors.items():
    l *= k**v

ans = 0
for a in A:
    ans += (l//a) % (10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

ans = 0
for a in A:
    ans += (l//a) % (10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

ans = 0
for a in A:
    ans += (l//a) % (10**9+7)

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

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten
# https://atcoder.jp/contests/abc152/tasks/abc152_e

from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
        ret += tmp

    print(ret%MODE)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# E - Flatten
# https://atcoder.jp/contests/abc152/tasks/abc152_e

from math import *
from collections import defaultdict

MAX_Ai = 10**6
MAX_PRIME = ceil(sqrt(MAX_Ai))
MODE = 10**9+7

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


def get_prime():
    # prime table
    ptb = [True] * MAX_PRIME
    ptb[0] = ptb[1] = False

    for i in range(2, ceil(sqrt(MAX_PRIME)) + 1):
        for j in range(i*2, MAX_PRIME, i):
            ptb[j] = False

    P = [ i for i, v in enumerate(ptb) if v == True]

    return P

def prime_factorization(n, P):
    factor = defaultdict(int)
    for p in P:
        while n % p == 0:
            factor[p] += 1
            n //= p

    if n != 1:
        factor[n] += 1

    return factor

def main():
    P = get_prime()    

    A_fact = list()
    lcm = defaultdict()
    for a in A:
        a_fact = prime_factorization(a, P)
        A_fact.append(a_fact)
        for prime, power in a_fact.items():
            if prime not in lcm:
                lcm[prime] = power
            else:
                if lcm[prime] < power:
                    lcm[prime] = power

    ret = 0
    for a_fact in A_fact:
        b_fact = {key: lcm[key] - a_fact.get(key, 0) for key in lcm.keys()}
        tmp = 1
        for prime, power in b_fact.items():
            tmp *= prime**power
            tmp %= MODE
        ret += tmp

    print(ret%MODE)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions 

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

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

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

ret = 0
for a in A:
    ret += (_lcm // a)
    ret %= MODE

print(ret)