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 math
N=input()
I=input()
a=I.split()
a.sort(reverse=True)
s=0
x=int(a[0])
for i in range(len(a)-1):
    b=int(a[i+1])
    z=x*b
    if(x<b):
        tmp=x
        x=b
        b=tmp
    r=x%b
    while r!=0:
        x=b
        b=r
        r=x%b
    x=z/b
u=[]
n=[]
c=0
l=0
o=int(math.sqrt(x))
pivot=sum(1 for y in a if int(y)>=o)
pivot-1
for j in range(len(a)):
    if(j>=pivot):
        c=0
        for k in reversed(range(l,len(u))):
            if(a[j]==u[k]):
                s=s+u[k]
                l=k
                c=1
                break
        if(c==0):
            s=s+x/int(a[j])
    else:
        u.append(x/int(a[j]))
        s=s+int(u[j])
print(int(s)%1000000007)

Submission status: Time Limit Exceeded

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

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

g=A[0]
l_1=A[0]
l_2=A[-1]
for i in range(N//2):
    g1=gcd(l_1,A[i])
    l_1=l_1*A[i]//g1
    g2=gcd(l_2,A[N-i-1])
    l_2=l_2*A[N-i-1]//g2
    
if N%2==1:
    g1=gcd(l_1,A[N//2])
    l_1=l_1*A[N//2]//g1
    
g=gcd(l_1,l_2)
l=l_1*l_2//g
    
ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
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)

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

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

print(ans)

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,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  MOD=10**9+7
  ans=0
  import numpy as np
  A=np.array(A)
  B=z//A%MOD
  print(sum(B)%MOD)
  
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys,fractions
sys.setrecursionlimit(10**5)
def input():
    return sys.stdin.readline()[:-1]

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

u = 10**9+7

from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

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

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

G = l[0]
for i in range(N-1,0,-1):
    G = fractions.gcd(G,l[i])
    if G==1:
        break

def division_binary_shift(a, b):
    """
    a // b

    :param a: dividend
    :param b: divisor
    :return: quotient
    """
    if a < b:
        return 0
    if b == 0:
        raise ZeroDivisionError

    q = 0
    sq = 1
    ori_b = b
    while a >= b:
        b <<= 1
        if a >= b:
            sq <<= 1
        else:
            b >>= 1
            a -= b
            q += sq
            sq = 1
            b = ori_b

    return q

gcd = G
L = [l[i]//gcd for i in range(N)]
lcm = lcm_list(L)

# print(lcm,gcd,'aaa')
ANS = 0
for i in range(N):
    elm = L[i]
    ANS += division_binary_shift(lcm,elm)
    ANS %= u
print(ANS)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import fractions 
from functools import reduce
arr = list(map(int,input().split()))

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

def lcma(numbers):
    return reduce(lcm_base, numbers, 1)
 
a = lcma(arr)

ans = [(a//i)%1000000007 for i in arr]
cnt=0
for i in ans:
    cnt += i %1000000007

print(cnt%1000000007)

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    res%=mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

def gcd(a, b):
    # 大きい方を被除数、小さい方を除数とする
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend

    # 最大公約数を見つけるまで繰り返す
    while dividend % divider != 0:
        # 除算を行い、その除数を次回の被除数、剰余を次回の除数として処理を繰り返す
        r = dividend % divider
        dividend = divider
        divider = r

    # 一方がもう一方を割り切れた時点で、その除数を最大公約数とみなせる
    return divider


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

L = reduce(lcm, a)

# print(L)

for i in range(n):
    ans += (L // a[i])
    # ans %= mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

div = 10**9 + 7
lcm_num = lcm(a)
ans = 0

for i in range(n):
    ans += (lcm_num // a[i]) % div

print(ans%div)

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin

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


n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
b=list(set(a))


lcm=b[0]

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

sm=0

for i in range(n):
	sm+=lcm//a[i]
	sm%=1000000007

print(sm)

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]

    b = 1
    l = ans

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

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

    # for i in a:
    #    b += o//i % MOD
    print(b % MOD)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
N=int(input())
A=list(map(int,input().split(' ')))
ans = 0
l = 1
mod = 10**9+7
for i in A:
    g = gcd(l,i)
    l = l*i//g
for i in A:
    ans += l//i
    ans %=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

x = 1
ans = 0
for i in range(N):
    tmp = gcd(x, A[i])
    # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    x = (x * A[i]) // tmp
    
b = 0
for i in range(N):
    b += x // A[i]
    
print(b%MOD)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
def lcm_base(x,y):
    return (x*y) // fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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

c = lcm_list(a)

b = []

for i in range(n):
    b.append((c//a[i])%(10**9+7))
print(sum(b)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout  

n = int(stdin.readline() )
arr=[int (i) for i in stdin.readline().split()]

def GCD(x, y): 
  
   while(y): 
       x, y = y, x % y 
  
   return x 
   
def findlcm(arr, n) :
    ans = arr[0]
    for i in range(1,n):
        ans = (((arr[i] * ans))/(GCD(arr[i], ans))); 
    return ans


lcm = findlcm(arr, n)

sum = 0
MOD = 1000000007
for i in range(n):
    sum = (sum + (lcm/arr[i])%MOD)%MOD

# print(int(sum))
sum = int(sum)
stdout.write(str(sum))

Submission status: Time Limit Exceeded

Solution code:

import fractions as ft
#import math as ft


prime = 10**9+7

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

an.sort()


lcm_ = 1
for a in an :
    lcm_ = a*lcm_ // ft.gcd(a, lcm_)
#    print(lcm_)
    
ans = 0
for a in an:
    ans += lcm_ // a
    ans = ans % prime if ans >= prime else ans

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) % mod
        ans %= mod

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

if N == 1:
    res = 1
else:
    l = lcm(A[0], A[1])
    for i in range(2, N):
        l = lcm(l, A[i])

    for i in range(N):
        res += l//A[i]

print(res % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from fractions import gcd
import numpy as np

MOD = 10**9+7

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


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

    lcm = reduce(lcm_base, a, 1)
    B = lcm // A

    print(np.sum(B) % MOD)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

lcm = 1
for i in range(n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
ans = 0
for i in range(n):
    ans += (lcm // a[i])
    ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]%MOD
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]%MOD
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
import fractions


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    MOD = 10 ** 9 + 7

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


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

    print(ans % MOD)



    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
#print(lcm_list(a))

n=lcm_list(a)

mod=10**9+7
ans=0
for i in range(m):
    ans+=n//a[i]%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:

from sys import stdin

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


n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))


lcm=a[0]

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

sm=0

for i in range(n):
	sm+=lcm//a[i]
	sm%=1000000007

print(sm)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from fractions import gcd
    a = int(input())
    l = list(map(int,input().split()))



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

    MOD = 10**9+7
    ans = 0
    t = 1
    for i in l:
        t = lcm(t,i)

    for i in l:
        ans +=t//i
        ans %=MOD
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
def lcm_for_list(numbers):
    from functools import reduce
    return reduce(lcm, numbers, 1)
 
def lcm(x, y):
    from fractions import gcd  # for Ver.3.4 or lower.
    return (x * y) // gcd(x, y)


if __name__ == "__main__":
    mod = 10**9+7
    N = int(input())
    A = list(map(int, input().split()))
    ll = lcm_for_list(A)
    ans = 0
    for a in A:
        ans += (ll//a)%mod
        ans %= mod
    print(int(ans))

Submission status: Time Limit Exceeded

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

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

n = int(input())
aa = list(map(int,input().split()))
           
l = lcm(*aa)        
aal = [l//ai % MOD for ai in aa] 

print(sum(aal) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd
import math
import collections
def input():
    return sys.stdin.readline()[:-1]
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass


def main():
    n=int(input())
    a=list(map(int,input().split()))
    mod=10**9+7
    # li=[0]*(max(a)+1)
    dic={}
    li=[]
    for i in range(n):
        tmp=collections.Counter(prime_factor(a[i]))
        li.append(tmp)
        # print(tmp)
        for j in list(tmp.keys()):
            if not j in dic:
                dic[j]=tmp[j]
            else:
                dic[j]=max(dic[j],tmp[j])
    ans=1
    # print(dic)
    for i in dic.keys():
        # print(dic[i],i)
        ans*=i**dic[i]
    # print(ans)
    cnt=0
    for i in range(n):
        tmp=1
        # print(li[i])
        for j in dic.keys():
            if j in li[i]:
                tmp*=j**(dic[j]-li[i][j])
            else:
                tmp*=j**dic[j]
            tmp%=mod
        cnt+=tmp
        cnt%=mod
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import fractions
def min_kou(a):
  ans = a[0]
  for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
  return ans

def main():
  N = int(input())
  A = list(map(int, input().split()))
  min_res = min_kou(A)
  ans = 0
  for i in A:
    ans += min_res // i
    if ans >= 1000000007:
      ans -= 1000000007
  print(ans % 1000000007)
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
from functools import reduce

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

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

def solve(N, A):
    mod = 10 ** 9 + 7
    lcm = lcm_list(A)
    ans = [lcm//a for a in A]
    return sum(ans) % mod


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    ans = solve(N, A)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in range(n):
    res += gcd//a[i]
    res%=mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    if x % y == 0:
        return x
    return (x * y) // fractions.gcd(x, y)

n = int(input())
a = list(map(int, input().split()))
a.sort()
LCM = 1
for i in a[::-1]:
    LCM = lcm(LCM, i)
ans = 0
for i in a:
    tmp = LCM // i
    ans += tmp
    ans %= 10 ** 9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

  from fractions import gcd
  from functools import reduce

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

  L = reduce(lcm, T)

  ans = 0

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

  print(ans % mod)

if __name__ == '__main__':
    main()

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,N):
      from fractions import gcd
      x = a[0]
      y=  a[N//2]
      for i in range(1, N//2):
          x = (x * a[i]) // gcd(x, a[i])
          y = (y * a[i+N//2]) // gcd(y, a[i+N//2])
      y = (y * a[-1]) // gcd(y, a[-1])
      return (x*y)//gcd(x,y)
  z=lcm(A,N)
  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:
from sys import stdin
MOD = 1000000007
def g(a, b):
 while b:a,b=b,a%b
 return a
def h(a,b):return(a*b)//g(a,b)
stdin.readline()
a=list(map(int,stdin.readline().split()))
l=1
for i in a:l=h(l,i)
s=0
for i in a:s=(s+l//i)%MOD
print(s)

Submission status: Time Limit Exceeded

Solution code:
import  fractions
from functools import reduce

def main():
    n=int(input())
    a=list(map(int,input().split()))
    tmp = lcm(*a)
    mod=10**9 + 7
    m=0
    ans=0
    for i, v in enumerate(a):
        m=tmp//v
        ans+=m%mod
    ans = ans % mod
    print(ans)

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)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]

ans = sum([lcm//a for a in As])
print(ans%mod)

Submission status: Time Limit Exceeded

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

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

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

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

sum = 0
for i in range(n):
  sum += ans//a[i]
  if sum >= 10**9+7:
    sum = sum %(10**9+7)
    
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions
from functools import reduce

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

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

if N==1:
  print(1)
else:
  alist.sort()
  lcm_alist=lcm_list(alist)
  
  answer=0
  last_a=-1
  last_b=-1
  for a in alist:
    b=last_b
    if a!=last_a:
      b=lcm_alist//a
      last_b=b

    answer=(answer+b)%(10**9+7)
    
  #print(blist)
  print(answer)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


MOD = 10**9+7

N = int(input())
A = list(map(int,input().split()))
#%%
def modinv(x,mod):
    return pow(x,mod-2,mod)

B = []
for a in A:
    b = modinv(a,MOD)
    B.append(b)

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

ans = 0

cur = 1
for a in A:
    cur =  lcm(cur,a)
for b in B:
    ans += cur*b
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce


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


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


def lcm_list(n):
    return reduce(lcm, n)


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

mod = 10 ** 9 + 7

L = lcm_list(a)
ans = 0
for i in a:
    ans = (ans + (L // i) % mod) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#-------------------------------------------------------------------
import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
#-------------------------------------------------------------------
MOD = 10**9+7
#-------------------------------------------------------------------
#gcd (最大公約数)(greatest common divisor)
#-------------------------------------------------------------------
# Python3.4以前なら、
from fractions import gcd
import fractions
from functools import reduce
#-------------------------------------------------------------------
#lcm (最小公倍数)
#-------------------------------------------------------------------
def lcm_base(a, b):
	return (a * b) // gcd(a, b)

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

def lcm_list(nums):
	return lcm(*nums)
#-------------------------------------------------------------------

n = int(input())

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

from itertools import groupby

#「groupby」を使って、
L = [[k, len(list(g))] for k, g in groupby(A)]

#p( L )
#	#[[12, 5]]
#	#[[999998, 1], [999999, 1], [1000000, 1]]

M=[]
for k,g in L:
	M.append(k)

#p(M)

x = lcm_list(M)

ans=0
for k,g in L:
	b = x // k
	ans+=(b*g)
	ans = ans % MOD


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    lcmA = 1
    for P in Primes:
        num = 0
        for PFs in PFss:
            if PFs[P] > num:
                num = PFs[P]
        lcmA *= pow(P, num, MOD)
        lcmA %= MOD

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

    invs = getInvs(10**6, MOD)

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

    print(ans)

solve()

Submission status: Time Limit Exceeded

Solution code:


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

def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)):
        g = gcd_core(g, arr[i])
    return g


def lcm_core(a,b):
    g = gcd_core(a,b)
    return (a*b)//g

def lcm(arr):
    if len(arr) == 1:
        return arr[0]
    else:
        newl = []
        ind = 0
        while True:
            if ind + 1 < len(arr):
                newl.append(lcm_core(arr[ind],arr[ind+1]))
                ind += 2
            else:
                newl.append(arr[ind])
                ind += 1
            if ind >= len(arr):
                break
        return lcm(newl)


n = int(input())

if n == 1:
    print(1)
else:
    arr = list(map(int,input().split()))
    l = lcm(arr)
    m = 10**9+7
    # print(l)
    # buf = []
    # for i in range(n):
    #     buf.append(l/arr[i])
    # print(buf)
    ans = 0
    for i in range(n):
        ans += l//arr[i]
        ans %= m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(u, v):

    k = 0
    while((0 == (u & 1)) and (0 == (v & 1))):
        k += 1
        u //= 2
        v //= 2

    if ((u & 1) == 0) :
        t = u // 2
    else:
        t = -v
    while ((t & 1) == 0):
        t //= 2
    if (t > 0) :
        u = t
    else :
        v = -t

    while (0 != t):
        # /* tが偶数である限り、2で割り続ける */
        while ((t & 1) == 0):
            t //= 2
        if (t > 0) :
            u = t
        else :
            v = -t

        t = u - v
    return u * (1 << k)

n = int(input())
a = list(map(int , input().split()))
l = a[0]
for i in range(1, n):
    l = l * a[i] // gcd(l, a[i])
ans = float('INF')
mod = 10**9+7

tmp = 0
for i in a:
    tmp = (tmp + (l // i)) % mod
print(tmp)

Submission status: Time Limit Exceeded

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

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

def saisho_ko_baisu(A,B):
    # A < B
    if B < A:
        A,B = B,A
    x = A*B
    r = B%A
    while r!=0:
        B = A
        A = r
        r = B%A
    return x//A

A.sort(reverse = True)
tmp = saisho_ko_baisu(A[0], A[1])
for i in range(2,N):
    if tmp % A[i] != 0:
        tmp = saisho_ko_baisu(tmp, A[i])
res = 0
for a in A:
    res += tmp//a

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

Submission status: Time Limit Exceeded

Solution code:


def main():
    from fractions import gcd
    import sys
    n=int(input())
    a = tuple(map(int, input().split()))
    ans = a[0]

    #mmm=10**9+7
    for i in range(1, n):
        ans = ans * a[i] // gcd(ans, a[i])

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

    print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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



n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g

for x in a:
  ans+=(l//x)%m

print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
import math
def main():

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

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

    def isprime(n):
        if n == 1: return False
        for i in range(2, int(math.sqrt(n))+1):
            if n % i == 0: return False
        return True

    B = set()
    ps = set()
    for i in range(N):
        if isprime(A[i]):
            ps.add(A[i])
        else:
            B.add(A[i])
    B = sorted(list(B))

    b = 1
    for i in range(len(B)):
        if b % B[i] != 0:
            g = gcd(b, B[i])
            b = b * B[i] // g
            c = b % mod

    for p in ps:
        if b % p != 0:
            b *= p

    ans = 0
    for i in range(len(A)):
        ans += (b // A[i]) % mod
        ans %= mod
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from fractions import gcd

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

x = 1
ans = 0
for i in range(N):
    tmp = gcd(x, A[i])
    # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    x = (x * A[i]) // tmp
    
b = 0
for i in range(N):
    b += x // A[i]
    
print(b%MOD)

Submission status: Time Limit Exceeded

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


    MOD = 10 ** 9 + 7

    def lcm_base(x, y):
        return (x * y) // 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()))

    tmp = lcm(*A)

    # print (tmp)
    ans = 0
    for a in A:
        ans += tmp // a
        ans %= MOD

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

def primes(n):
    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
    return [i for i in range(n + 1) if is_prime[i]]

import copy
N = int(input())
Ps = list(map(int,input().split(" ")))
org_Ps = copy.deepcopy(Ps)
prime_nums = primes(10 ** 5)


mul = 1
used = False
for p in prime_nums:
    used = False
    for i in range(len(Ps)):
        if Ps[i] %p == 0:
            Ps[i]//=p
            if not used:
                used = True
                mul *= p

MOD = 10 ** 9 + 7
g = 1

for p in Ps:
    g = g* p // fractions.gcd(g, p)
g *= mul
ans = 0

for p in org_Ps:
    ans += g//p
    ans %= MOD
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions

input = sys.stdin.readline

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


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

index = A[0]

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

MOD = 10**9 + 7

ans = 0

for a in A:
    ans += (index//a)

print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
mod =M
import sys
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
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*power(p,d[p]-ps[p])%M)%M
    r = (r+t)%M
print(r)