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:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


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


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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    k = A[0]
    for a in A[1:]:
        k *= a//gcd(k, a)
    ans = modint(0)
    for a in A:
        ans += k//a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
al = list(map(int,input().split()))
al = sorted(al)
p = al[0]
for i in range(1, n):
    p = p * al[i] // fractions.gcd(p, al[i])

ans = 0

for a in al:
    ans += p // a

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
l = list(map(int,input().split()))
if n == 1:
    print(1)
    exit()

def lcm(a,b):
    return a*b/fractions.gcd(a,b)
ans = l[0]
for i in range(1,n):
    ans = lcm(ans,l[i])
    

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7


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

cnt=0
b=[ans//a[i] for i in range(n)]
print(sum(b)%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7


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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

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 a[1:]:
        ans = ans *i // gcd(ans, i)

    result=0
    for item in a:
      result+=ans//item

    print(result%mmm)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD=10**9+7

primes=[]
is_prime=[True]*(10**6)
for i in range(2,10**6):
    if not is_prime[i]: continue
    primes.append(i)
    for j in range(2*i,10**6,i):
        is_prime[j]=False

F=[[0 for _ in range(len(primes))] for __ in range(N)]
LCM=[0 for _ in range(len(primes))]
for i in range(N):
    n=A[i]
    f=F[i]
    for j,p in enumerate(primes):
        while n%p==0:
            f[j]+=1
            n//=p
        LCM[j]=max(LCM[j],f[j])

ans=0
for i in range(N):
    tmp=1
    f=F[i]
    for j,p in enumerate(primes):
        tmp=tmp*pow(p,LCM[j]-f[j],MOD)%MOD
    ans=(ans+tmp)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
	return gcd(b,a%b) if b else a
n = int(input())
a = list(map(int,input().split()))
lcm = 1
for v in a:
	lcm *= v//gcd(v,lcm)
ans = 0
for v in a:
	ans += lcm // v
print(ans%1000000007)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n = int(input())
a = list(map(int, input().split()))
 
def lcm(x, y):
	return (x // fractions.gcd(x, y))*y
 
num = a[0]
for i in range(1, n):
	num = lcm(num, a[i])
 
ans = 0
for i in range(n):
	ans += (num//a[i]) % 1000000007
	if ans > 1000000007:
		ans = ans%1000000007
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
  ans = 0
  n = int(input())
  a = tuple(map(int, input().split()))
  ov = 10**9+7
  from fractions import gcd
  def lcm(a):
      x = a[0]
      ln = len(a)
      for i in range(1, ln):
          x = (x * a[i]) // gcd(x, a[i])
      return x
  l = lcm(a)
  for i in range(n):
    ans += l//a[i]%ov
  print(ans%ov)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
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
 
l = lcm(a)
count = 0
for i in range(len(a)):
    count += (l//a[i])
    count = count % (1000000007)
print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

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

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

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

lcm_ = lcm_list(a)
b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

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

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

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

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

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

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


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


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


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    k = A[0]
    for a in A[1:]:
        k = lcm(k, a)
    ans = modint(0)
    for a in A:
        ans += k//a
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7


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

cnt=0
for i in range(n):
    cnt+=ans//a[i]
    cnt%=mod
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b): return a * b // gcd(a, b)
def lcm_list(A): return reduce(lcm, A)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
def gcd(a, b):
    while(b > 0):
        a = a%b
        c = b
        b = a
        a = c
    return a

n = int(input())
s = input()

s = s.split(" ")

l = int(s[0])

for i in range(1, n):
    l = (l*int(s[i]))//gcd(l, int(s[i]))

ans = 0
for x in s:
    x = int(x)
    ans = (ans +l//x)%mod

print(ans%mod)

Submission status: Time Limit Exceeded

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

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

n=max(A)

#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)

lcm=[0]*len(table)



for i in range(N):
    for j in range(len(table)):
        temp=0
        a=A[i]
        while a%table[j]==0:
            temp+=1
            a=a//table[j]
        lcm[j]=max(lcm[j],temp)
        
l=1
for j in range(len(table)):
    l*=pow(table[j],lcm[j])
    

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=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 lcm(numbers):
    return reduce(lcm_base, numbers, 1)
    
a = lcm(arr)
 
ans = 0
 
for i in range(n):
    ans+= a//arr[i]
    
print(ans %(1000000000+7))

Submission status: Time Limit Exceeded

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

N = int(input())

#a, b, c = (int(i) for i in input().split())  
a = [int(i) for i in input().split()] 
#e = [[int(i) for i in input().split()] for i in range(n)] 

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

for j in range(N):
    total += ans//a[j]
    total %= (10**9+7)

print(int(total%(10**9+7)))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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



def main():
    N = int(input())
    a = [int(i) for i in input().split()] 
    M = 10**9+7
    ans = a[0]
    total = 0
    for i in range(1, N):
        ans = ans * a[i] // fractions.gcd(ans, a[i])

    for j in range(N):
        total += ans//a[j]
        total %= (10**9+7)

    print(int(total))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

mod = 10 ** 9 + 7
N = 1000002

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

base = a[0]
for ai in a:
    base = lcm(base, ai)
ans = 0
for ai in a:
    ans = (ans + base * inv_t[ai]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from functools import reduce

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
pf_A = [prime_factorization(a) for a in A]
lcm = reduce(lambda x,y: x | y, pf_A)
for fact in pf_A:
    temp = lcm - fact
    t = 1
    if temp.items():
        for x, y in temp.items():
            t *= pow(x, y, MOD)
        ans += t
        ans %= MOD
    else:
        ans += 1
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = 1
sum = 0
for i in range(N):
    ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
    sum += ans//a
print(sum%(7+10**9))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
mod = pow(10, 9)+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  m = A[0]
  for i in range(1, n):
    m = m // gcd(m, A[i]) * A[i]
  ans = 0
  for i in A:
    ans += m//i
  print(ans%mod)
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
mod = 10**9 + 7
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
b = []
for i in range(n):
    an = ans // a[i]
    b.append(an)

print(sum(b) % mod)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
MOD = 1000000000+7

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

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

a_lcm = A[0]
for a in A[1:]:
  a_lcm = lcm(a_lcm, a)

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

mod = 10 ** 9 + 7

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

count = 0
for i in a:
    count += l // i
    count = count % mod

print(count)