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
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    
    def factorization(n):
        arr = defaultdict(int)
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr[i] = cnt

        if temp!=1:
            arr[temp] = 1

        if not arr:
            arr[n] = 1

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from collections import defaultdict
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: dict A[i]の素因数分解
    A2Factor = [defaultdict(int) for _ in range(N)]
    
    def factorization(n, idx):
        """
        素因数分解
        """
        temp = n
        flag = 0
        for i in range(2, int(sqrt(n))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                flag = 1
                LCM[i] = max(LCM[i], cnt)
                A2Factor[idx][i] = cnt
        if temp!=1:
            LCM[temp] = max(LCM[temp], 1)
            A2Factor[idx][temp] = 1 
        if not flag:
            LCM[n] = max(LCM[n], 1)
            A2Factor[idx][n] = 1
        return LCM, A2Factor

    for idx in range(N):
        LCM, A2Factor = factorization(A[idx], idx)

    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

Submission status: Time Limit Exceeded

Solution code:
n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import Counter
from math import sqrt, ceil
def factors(x):
    c = Counter()
    while x % 2 == 0:
        c[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            c[i] += 1
            x //= i
    if x > 1:
        c[x] += 1
    return c

factors_of_aa = list(map(factors, aa))

lcm = Counter()
for factors_of_a in factors_of_aa:
    lcm |= factors_of_a

ans = 0
for factors_of_a in factors_of_aa:
    factors_to_add = lcm - factors_of_a
    to_add = 1
    for factor, cnt in factors_to_add.items():
        to_add *= pow(factor, cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

mod=1000000007
n=input();
arr = list(map(int, raw_input().split()))
l=arr[0];
for i in arr:
    x=gcd(l,i)
    l=(l*i)/x
    
ans=0
#print l
for i in arr:
    b=l/i
    ans=(ans%mod + b%mod)%mod
ans=(ans%mod +mod)%mod
print ans

Submission status: Time Limit Exceeded

Solution code:
from math import *
from functools import reduce
def lcm(a,b):
  return a*b//gcd(a,b)
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=reduce(lcm,a)
ans=0
for i in a:
  ans+=c//i%mod
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
if N == 1:
  print(1)
  exit(0)
  
mod = int(1e9+7)
#### 
# https://note.nkmk.me/python-gcd-lcm/
from math import gcd
from functools import reduce

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)
  
L = lcm_list(A)
ans = 0
for a in A:
  ans += L // a
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import defaultdict, Counter

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

N = int(input())
A = [int(i) for i in input().split()]
v_list = []
mod = 10 ** 9 + 7
LCM_dict = defaultdict(int)
for i in range(N):
    prime_cnt = Counter(prime_factorize(A[i]))
    for k, v in prime_cnt.items():
        LCM_dict[k] = max(LCM_dict[k], v)
    v_list.append(prime_cnt)
ans = 0
for i in range(N):
    prime_cnt = v_list[i]
    tmp_value = 1
    for k, v in LCM_dict.items():
        cnt = 0 if k not in prime_cnt.keys() else prime_cnt[k]
        tmp_value = pow(k, v - cnt) * tmp_value
        tmp_value = tmp_value % mod
    ans += tmp_value
    ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
A = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
LCM = A[0]
for i in range(N - 1):
    LCM = (LCM * A[i + 1]) // math.gcd(LCM, A[i + 1])
ans = 0
for i in range(N):
    ans = ans + (LCM // A[i])
    ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    A, B = [], {}
    for i in range(n):
        d = {}
        for j in range(2,int(a[i]**0.5)+1):
            if a[i]%j==0:
                cnt = 0
                while a[i]%j==0:
                    cnt += 1
                    a[i] = a[i]//j
                d[j] = cnt
                if B.get(j)==None:
                    B[j] = cnt
                else:
                    if B[j]<cnt:
                        B[j] = cnt
        if a[i]!=1:
            d[a[i]] = 1
            if B.get(a[i])==None:
                B[a[i]] = 1
        A.append(d)
    ans = 0
    for i in range(n):
        d = A[i]
        a = 1
        for k in B.keys():
            if d.get(k)!=None:
                a *= pow(k,B[k]-d[k],mod)
            else:
                a *= pow(k,B[k],mod)
            a = a%mod
        ans += a
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        k = lcm[p] - ps[i].get(p, 0)
        prod = (prod * (p ** k)) % mod
    ret = (ret + prod) % mod

print(ret)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

kb = 1
for k, v in fa.items():
    kb *= pow(k, v)

mod = 10**9+7
s = sum(pow(a, mod-2, mod) for a in A)
print(s*kb%mod)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

ans = 0
mod = 10**9+7
for i in range(n):
    t = 1
    fb = fa - p[i]
    for k, v in fb.items():
        t *= pow(k, v, mod)
        t %= mod
    ans += t % mod
    ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

ans = 0
mod = 10**9+7
for i in range(n):
    t = 1
    fb = fa - p[i]
    for k, v in fb.items():
        t *= pow(k, v, mod)
    ans += t % mod
    ans %= mod
print(ans % mod)

Submission status: Time Limit Exceeded

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p <= ai * ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        k = lcm[p] - ps[i].get(p, 0)
        prod = (prod * (p ** k)) % mod
    ret = (ret + prod) % mod

print(ret)

Submission status: Time Limit Exceeded

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p <= ai * ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

ret = 0
for i in range(n):
    prod = 1
    for p in lcm:
        for k in range(lcm[p] - ps[i].get(p, 0)):
            prod = (prod * p) % mod
    ret = (ret + prod) % mod

print(ret)

Submission status: Time Limit Exceeded

Solution code:
# A1〜ANの最小公倍数を求める
# Aiにかけて最小公倍数にすることができるBiを求める
# Biを足す
import math
MOD = 10**9 + 7

N = int(input())
A = [int(s) for s in input().split()]


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


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

result = 0

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

print(result)

Submission status: Time Limit Exceeded

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

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

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

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

mod = 1000000007
ret = 0
for ai in a:
    ret = (ret + l // ai) % mod
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
p = []
for a in A:
    tt = prime_factorize(a)
    fa = fa | tt
    p.append(tt)

ans = 0
mod = 10**9+7
for i in range(n):
    t = 1
    fb = fa - p[i]
    for k, v in fb.items():
        t *= pow(k, v, mod)
    ans += t % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
for a in A:
    fa = fa | prime_factorize(a)

ans = 0
mod = 10**9+7
for a in A:
    t = 1
    fb = fa - prime_factorize(a)
    for k, v in fb.items():
        t *= pow(k, v, mod)
    ans += t % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import collections
n = int(input())
A = list(map(int, input().split()))

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

fa = collections.Counter()
for a in A:
    fa = fa | prime_factorize(a)

ans = 0
mod = 10**9+7
for a in A:
    t = 1
    fb = fa - prime_factorize(a)
    for k, v in fb.items():
        t *= (k**v % mod)
    ans += t % mod
print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

mod = 1000000007

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

n=int(input())

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

memo = a[0]

for i in range(1,n):
    memo = lcm(memo,a[i])

ans = 0

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

class FactInv:
    def __init__(self, N, MOD=MOD):
        fact, inv = [1]*(N+1), [None]*(N+1)
        for i in range(1, N+1): fact[i] = fact[i - 1] * i % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N)[::-1]: inv[i] = inv[i + 1] * (i + 1) % MOD
        self.N, self.MOD, self.fact, self.inv = N, MOD, fact, inv

    def perm(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD

class Eratosthenes:
    # https://cp-algorithms.com/algebra/prime-sieve-linear.html
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N = I()
    A = LI()

    era = Eratosthenes(max(A))
    lcm = Counter()

    for ai in A:
        cai = Counter(era.factors(ai))
        for k in cai.keys():
            lcm[k] = max(lcm[k], cai[k])

    ans = 0
    for i in range(N):
        cai = Counter(era.factors(A[i]))
        tmp = 1
        for k, v in lcm.items():
            tmp = tmp * pow(k, v - cai[k], MOD) % MOD
        ans = (ans + tmp) % MOD
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

class FactInv:
    def __init__(self, N, MOD=MOD):
        fact, inv = [1]*(N+1), [None]*(N+1)
        for i in range(1, N+1): fact[i] = fact[i - 1] * i % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N)[::-1]: inv[i] = inv[i + 1] * (i + 1) % MOD
        self.N, self.MOD, self.fact, self.inv = N, MOD, fact, inv

    def perm(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD

class Eratosthenes:
    # https://cp-algorithms.com/algebra/prime-sieve-linear.html
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N = I()
    A = LI()

    era = Eratosthenes(max(A))
    lcm = Counter()

    for ai in A:
        cai = Counter(era.factors(ai))
        for k in cai.keys():
            lcm[k] = max(lcm[k], cai[k])

    B = [copy.copy(lcm) for _ in range(N)]
    for i in range(N):
        B[i].subtract(era.factors(A[i]))


    ans = 0
    for bi in B:
        tmp = 1
        for k, v in bi.items():
            tmp = tmp * pow(k, v, MOD) % MOD

        ans = (ans + tmp) % MOD
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


mod = 10**9+7


def prime(x):
    pf = defaultdict(int)
    for i in range(2, int(x**0.5)+1):
        while x % i == 0:
            pf[i] += 1
            x //= i
    if x > 1:
        pf[x] = 1
    return pf


def lcm(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] = max(xx[k], yy[k])
    return xx


def flat(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] -= yy[k]
    ans = 1
    for k, v in xx.items():
        ans = (ans*(k**v)) % mod
    return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = list(map(prime, a))
    lcms = reduce(lcm, a)
    ans = 0
    for aa in a:
        ans += flat(lcms,aa)
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


mod = 10**9+7


def prime(x):
    pf = defaultdict(int)
    for i in range(2, int(x**0.5)+1):
        while x % i == 0:
            pf[i] += 1
            x //= i
    if x > 1:
        pf[x] = 1
    return pf


def lcm(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] = max(xx[k], yy[k])
    return xx


def flat(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] -= yy[k]
    ans = 1
    for k, v in xx.items():
        ans = (ans*(k**v)) % mod
    return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a = list(map(prime, a))
    lcms = reduce(lcm, a)
    ans = 0
    for aa in a:
        ans += flat(lcms,aa)
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if count[p] == 0 and b%p == 0:
        baisu.append(p)
      c = 0
      while b % p == 0:
        b //= p 
        c += 1 
      if c > count[p]:
        count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

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

    return d


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

ctr = defaultdict(int)
buf = []
for n in X:
    d = prime_factor(n)
    buf.append(d)
    for key in d:
        ctr[key] = max(ctr[key], d[key])

ans = 0
for i, n in enumerate(X):
    cur = 1
    for key in ctr:
        cnt = ctr[key] - buf[i][key]
        if cnt > 0:
            cur = cur * pow(key, cnt, MOD) % MOD

    ans += cur
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

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

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

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

b = lcm(*a)

ans = 0
for i in range(N):
    ans = (ans + b // a[i]) % mod

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
def main():
    n=I()
    lis=LI()
    def prime_factorize(n):
        a = []
        while n % 2 == 0:
            a.append(2)
            n //= 2
        f = 3
        while f * f <= n:
            if n % f == 0:
                a.append(f)
                n //= f
            else:
                f += 2
        if n != 1:
            a.append(n)
        return a
    lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
    C=Counter([])
    for i in range(n):
        x=lists[i]
        for j in x.keys():
            C[j]=max(C[j],x[j])
    #print(C)
    
    ans=0
    for i in range(n):
        x=lists[i]
        y=1
        for j in C.keys():
            y=(y*pow(j,C[j]-x[j],mod))%mod
        #print(y%mod)
        ans=(ans+y)%mod
    print(ans%mod)
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
C=Counter([])
for i in range(n):
    x=lists[i]
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=lists[i]
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j],mod))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
C=Counter([])
for i in range(n):
    x=lists[i]
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=lists[i]
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j]))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lists=[prime_factorize(lis[i]) for i in range(n)]
C=Counter([])
for i in range(n):
    x=Counter(lists[i])
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=Counter(lists[i])
    y=1
    for j in C.keys():
        y=(y*pow(j,C[j]-x[j],mod))%mod
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)