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:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))


# 素因数分解
def prime_factorization(n):
    fact=[]
    fact=defaultdict(int)
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            # fact.append(i)
            fact[i]+=1
            # print(n,i)
    if n!=1:
        fact[n]+=1
    return fact
def main():
    N=I()
    A=LI()

    lcm = defaultdict(int)
    for a in A:
        tmp = defaultdict(int)
        p = prime_factorization(a)
        union = lcm.keys() | p.keys()
        for k in union:
            tmp[k] = max(p[k],lcm[k])
        lcm = tmp
    L = ModInt(1)
    for l,v in lcm.items():
        L *= l**v
    ans = ModInt(0)
    for a in A:
        ans += L/a
    print(ans)
    # print(L.x%mod)
    #2021049

    # mul = ModInt(1)

    # lcm = ModInt(1)
    # for a in A:
    #     lcm = lcm/gcd(a,lcm.x)*a
    #     # lcm%=mod

    # print(lcm)
    # ans = ModInt(0)
    # for a in A:
    #     ans += lcm/a
    #     print(lcm/a)
    # # print(ans)

    # L = 1
    # for a in A:
    #     L *= a//gcd(L,a)
    # print(prime_factorization(L))
    # print(L%mod)
    # for a in A:
    #     print((L//a)%mod)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce, lru_cache


@lru_cache(maxsize=2**18)
def GCD(x, y):
    if y == 0:
        return x
    else:
        return GCD(y, x % y)


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


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
n = int(input())
A = []
A = list(map(int, input().split()))
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)
Z = lcm(*A)
ans = sum(Z//a%mod for a in A)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
mod=10**9 + 7
N=10**6+1
inv_t=[0]+[1]
for i in range(2,N):
    inv_t+=[inv_t[mod%i]*(mod-int(mod/i))%mod]
n=int(input())
A=list(map(int,input().split()))
l=[0]*10**6
for a in A:
    for i in range(2,int(math.sqrt(a))+1):
        c=0
        while a%i==0:
            c+=1
            a//=i
        l[i]=max(l[i],c)
    if a!=1:
        l[a]=max(l[a],1)
lcm=1
for i in range(10**6):
    if l[i]!=0:
        lcm=(lcm*(i**l[i]))%mod
ans=0
for a in A:
    ans=(ans+lcm*inv_t[a])%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#from fractions import gcd
from collections import Counter
mod = 10**9+7
def inv(a):
  return pow(a,mod-2,mod)
def prm(a):
  if a == 1 or a == 4:
    return False
  for i in range(2,int((a)**0.5+1)):
    if a%i == 0:
      return False
  else:
    return True
prime = []
for i in range(1,10**4+1):
  if prm(i):
    prime.append(i)
def sepa(a):
  ans = []
  while a>1:
    for x in prime:
      if a%x == 0:
        ans.append(x)
        a = a//x
        break
  return Counter(ans)
n = int(input())
a = list(map(int,input().split()))
f = [inv(a[i]) for i in range(n)]
lcm = sepa(1)
for i in range(n):
  x = sepa(a[i])
  for y,z in x.items():
    if z>lcm[y]:
      lcm[y] = z
k = 1
for i,j in lcm.items():
  k = k*(i**j)%mod
print(k*sum(f)%mod)

Submission status: Time Limit Exceeded

Solution code:
# ABC152e


def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10 ** 6)
    MOD = 10**9+7

    from fractions import gcd

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

    from functools import reduce

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

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

    ans = a[0]

    for i in range(1, n):
        ans = ans * a[i] // gcd(ans, a[i])
    # print(ans)
    o = ans
    # print(o)
    b = 0
    for i in a:
        b += o//i % MOD
    print(b % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

#from math import gcd
from fractions import gcd

def main():
	n=int(input())
	A=list(map(int,input().split()))
	A.sort()
	a=1
	for i in A:
		a=a*i//gcd(a, i)
	ans=0
	for i in A:
		ans+=(a//i)
		ans%=mod
	print(ans)
	
	
	
	
	
	


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    c=0
    for x in A[1:]:
        l=l*x//gcd(l,x)
    c+=l//MOD
    l%=MOD
    ans=0
    for x in A:
        ans+=l//x
        ans+=MOD//x*c
        ans+=(MOD%x*c+l%x)//x
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

import fractions
from functools import reduce

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

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

lcmv = 1
b_bar = []
for num in a:
    lcmv = lcm(num, lcmv)

ans = 0
for num in a:
    if num > lcmv:
        lcmv += 1000000007
    ans += lcmv // num
    ans %= 1000000007
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7

def extgcd(a,b): #互いに素なa,bについて、a*x+b*y=1の一つの解
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

def mod_inv(a,mod): # (x/a)%MODをしたい時は x%MOD * mod_inv(a,MOD)%MOD
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod


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

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

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

lcm_ = a[0]
ans = 1
for i in range(1,n):
    if lcm_ % a[i] != 0:
        if lcm_%MOD * mod_inv(a[i],MOD)%MOD != 0:
            lcm_new = lcm(lcm_, a[i])
            ans = ans*(lcm_new%MOD *mod_inv(lcm_,MOD)%MOD)
            lcm_ = lcm_new
    ans += lcm_%MOD * mod_inv(a[i], MOD)%MOD

print(ans%MOD)

Submission status: Time Limit Exceeded

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

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

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

def lcm(a):
    #from fractions import gcd
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x


n = int(input())
A = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  N=int(input())
  A=list(map(int,input().split()))
  def lcm(a):
      from fractions import gcd
      x = a[0]
      for i in range(1, len(a)):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  z=lcm(A)
  MOD=10**9+7
  ans=0
  for i in range(N):
    ans+=z//A[i]%MOD
  print(ans%MOD)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
N = int(input())
A = tuple(map(int, input().split()))

mod = 10**9+7
lcm = 1
B = [0]*N

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

ans = 0

for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def main():
  _=input()
  a=tuple(map(int,input().split()))
  aset=set(a)
  a1=a[0]
  fgcd=fractions.gcd
  for i in aset:
    if a1%i:
        a1=(i*a1)//fgcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
from functools import reduce

res = 1e9 + 7

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

ans = int(As[0] % res)
for i in range(1, N):
     ans = ans // (fractions.gcd(ans, As[i]) % res) * (As[i] % res)

# lcm_num = lcm_list(As)

sum = 0

for i in range(N):
  sum += int((ans / As[i]) % res)

print(int(sum % res))

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
ans = 0
b = []
n = int(input())
a = list(map(int,input().split()))
kari = a[0]
for i in a:
    kari = lcm(kari,i)
for i in a:
    b.append(kari//i)
print(sum(b)%1000000007)

Submission status: Time Limit Exceeded

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

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

N = int(input())
A =list(map(int,input().split()))
 
if N== 1:
    print(1)
    exit(0)
else:
    tmp = lcm(A[0],A[1])
    for i in range(1,N):
        if tmp // A[i] != 0:
            tmp = lcm(tmp,A[i])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-math.sqrt(n)//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

n = inp()
a = inpl()
g = 1
res = 0
d = defaultdict(int)
for i in a:
    arr = factorization(i)
    r = 1
    # print(arr)
    # for l in arr:
    #     r *= l[0] * l[1]
    # print(r)
    for l in arr:
        if d[l[0]] < l[1]:
            d[l[0]] = l[1]
# print(d)
for key in list(d):
    g *= key ** d[key]
for i in range(n):
    res += g//a[i]
    res %= mod
print(res)

Submission status: Time Limit Exceeded

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

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

import fractions
ans = A[0]
for a in A[1:]:
    ans = ans * a // fractions.gcd(ans, a)

sum_b = 0
for a in A:
    sum_b += ans // a

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

def prime_factor(n):
    c = Counter()
    i = 2
    while i * i <= n:
        while (n % i == 0):
            c[i] += 1
            n = n//i
        i += 1
    if n != 1:
        c[n] += 1

    return c

MOD = 10**9+7

N = int(input())
A = list(map(int, input().split()))
ans = 0
prime_list = []
max_list = Counter()
for a in A:
    c = prime_factor(a)
    prime_list.append(c)
    for key, val in c.items():
        max_list[key] = max(max_list[key], val)
for c in prime_list:
    tmp = 1
    for key, val in max_list.items():
        tmp = (tmp * pow(key, (val-c[key]), MOD))%MOD
    ans = (ans + tmp)%MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    from fractions import gcd

    def lcd(x, y):
        g = gcd(x, y)
        return x * y // g
    
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    l = 1
    for e in a:
        l = lcd(l, e)

    ans = 0
    for e in a:
        ans += l // e
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
P = 10 ** 9 + 7
p = 10 ** 9 + 7
mo = P
inv_t = [0]+[1]
#for i in range(2,1000009):
  #inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#print("俺のソフト")

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

M = a[0]
for i in range(1, n):
    M = M * a[i] // gcd(M, a[i])

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

print(ans)

Submission status: Time Limit Exceeded

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


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
N = int(input())
A = tuple(map(int, input().split()))

mod = 10**9+7
lcm = 1
B = [0]*N

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

ans = 0

for i in range(N):
    ans += (lcm * inv_t[A[i]])
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

debug = False

if debug:
    n = 10000
    aaa = [ a*100+1 for a in range(n) ]
else:
    n = int(input())
    aaa = get_nums_l()

# gcd_ = reduce(gcd, aaa)
# x = [ a//gcd_ for a in aaa ]
# lcm_ = gcd_ * reduce(lambda a,b: a*b, x)
lcm_ = (lcm(aaa))

ans = 0
for a in aaa:
    ans = (ans + lcm_//a) % (10**9+7)
print(ans % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
#mint
class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

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

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

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

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

    __rmul__ = __mul__

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

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

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))


# 素因数分解
def prime_factorization(n):
    fact=[]
    fact=defaultdict(int)
    for i in range(2, int(sqrt(n)) + 1):
        while n % i == 0:
            n //= i
            # fact.append(i)
            fact[i]+=1
            # print(n,i)
    if n!=1:
        fact[n]+=1
    return fact
def main():
    N=I()
    A=LI()

    lcm = defaultdict(int)
    for a in A:
        tmp = defaultdict(int)
        p = prime_factorization(a)
        # print(lcm.keys())
        # print(p.keys())
        union = lcm.keys() | p.keys()
        # print(union)
        for k in union:
            # print(k)
            tmp[k] = max(p[k],lcm[k])
        lcm = tmp
        # print(lcm)
    L = ModInt(1)
    # print(type(lcm))
    for l,v in lcm.items():
        L *= l**v
    ans = ModInt(0)
    for a in A:
        ans += L/a
    print(ans)
    # print(L.x%mod)
    #2021049

    # mul = ModInt(1)

    # lcm = ModInt(1)
    # for a in A:
    #     lcm = lcm/gcd(a,lcm.x)*a
    #     # lcm%=mod

    # print(lcm)
    # ans = ModInt(0)
    # for a in A:
    #     ans += lcm/a
    #     print(lcm/a)
    # # print(ans)

    # L = 1
    # for a in A:
    #     L *= a//gcd(L,a)
    # print(prime_factorization(L))
    # print(L%mod)
    # for a in A:
    #     print((L//a)%mod)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def gcd(m, n):
  r=m%n
  return gcd(n, r) if r else n
def lcm(m, n):
  return m*n//gcd(m, n)

def main():
  n=I()
  l=LI()

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

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

# main()
print(main())

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
lcm = 1
for i in range(n):
  lcm = lcm * a[i] // gcd(lcm, a[i])
for i in range(n):
  cnt += lcm // a[i]
  cnt %= 10**9+7
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import fractions
mod = 1000000007

def add(a, b):
    return (a + b) % mod

n = int(input())
a = list(map(int,input().split()))
ans = a[0]
ans_ans = 0
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
for j in range(0, n):
  b = ans // a[j]
  ans_ans = add(ans_ans,b)
  
print(ans_ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table.append((i,c))
        i += 1
    if n > 1:
        table.append((int(n), 1))
    return table

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

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce, lru_cache


@lru_cache(maxsize=2**14)
def GCD(x, y):
    if y == 0:
        return x
    else:
        return GCD(y, x % y)


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


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

M = 10 ** 9 + 7

cache = {}

def calc_factors(n):
	org_n = n
	if n in cache:
		return cache[n]
	max = math.ceil(math.sqrt(n))
	data = {}
	x = 2
	while x <= max:
		if n % x == 0:
			if x in data:
				data[x] += 1
			else:
				data[x] = 1
			n //= x
			max = math.ceil(math.sqrt(n))
		else:
			x += 1
	if n != 1:
		if n in data:
			data[n] += 1
		else:
			data[n] = 1
	cache[org_n] = data
	return data

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

total_factors = {}
factors_list = []

for A in A_list:
	factors = calc_factors(A)
	factors_list.append(factors)
	for factor, count in factors.items():
		if factor not in total_factors:
			total_factors[factor] = count
		elif total_factors[factor] < count:
			total_factors[factor] = count

total = 0
for A, factors in zip(A_list, factors_list):
	B = 1
	for factor, count in total_factors.items():
		if factor in factors:
			count -= factors[factor]
		for _ in range(count):
			B = (B * factor) % M
	total = (total + B) % M

print(total)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = [int(x) for x in input().split()]
A = sorted(A, reverse=True)
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)
mod = 7 + 10 ** 9
lcm = lcm(*A)
ans = 0
for i in A:
    ans += lcm // i
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7


def main():
    nok = 1
    n = int(input())
    a = [int(i) for i in input().split()]
    for i in a:
        nok = nok * i // gcd(nok, i)
    ans = 0
    for i in a:
        ans = (ans + nok // i) % mod
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

num = int(input())
A = [int(s) for s in input().split()]
ans = A[0]
for i in range(1,num):
    ans = ans * A[i]//fractions.gcd(ans,A[i])
B = [ans//A[s] for s in range(num)]
print(sum(B)%(10**(9)+7))

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007

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

def lcm(a, b):
    m = a // gcd(a, b)
    m *= b
    # m %= mod
    return m

def modinv(a):
    b = mod
    u = 1
    v = 0
    while (b):
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u

    u %= mod
    if (u < 0):
        u += mod
    return u

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))

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

    ans = 0
    for i in range(N):
        r = lc * modinv(A[i])
        # r = lc // A[i]
        ans += r
        ans %= mod

    print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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




n = int(input())
A = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import fractions
def main():
  _=input()
  a=tuple(map(int,input().split()))
  a1=a[0]
  fgcd=fractions.gcd
  for i in a:
    if a1%i:
        a1=(i*a1)//fgcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools
import collections
import fractions
N = int(input())
A = [int(i) for i in input().split()]


C = collections.Counter(A)

mod = 10**9 + 7

# lcm = 1
# for a in C.keys():
#     lcm = lcm*a//fractions.gcd(lcm, a)
# print(lcm)


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


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(list(C.keys()))

ans = 0
for k, v in C.items():
    ans += lcm//k*v
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

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

def main():
  n=I()
  l=LI()

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

  ans=0
  for x in l:
    ans+=a//x

  return ans%mod

# main()
print(main())

Submission status: Time Limit Exceeded

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


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


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


mod = 10**9+7
lcm = 1
B = [0]*N

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

ans = 0

for i in range(N):
    ans += (lcm * modinv(A[i]))
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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


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

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

l = A[0]
for a in A:
  if l%a != 0:
    l = lcm(l, a)

B = []
for a in A:
  B.append((l//a) % MOD)

print(sum(B)%MOD)

Submission status: Time Limit Exceeded

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

DIV=10**9+7

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

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

sums=0
L=1
for i in range(N):
  newL=lcd(L,A[i])
  if newL!=L:
    sums=(sums*(newL//L)+newL//A[i])%DIV
    L=newL
  else:
    sums=(sums+newL//A[i])%DIV

print(sums)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import fractions
import sys
sys.setrecursionlimit(20000)

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


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

N = int(input())
A = list(map(int, input().split()))
B = [0 for _ in range(N)]
mod = 10**9+7

ll = lcm_list(A)
ans = 0
for i in range(N):
    B[i] = (ll//A[i])%mod
    ans += B[i]
print(int(ans%mod))