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: Runtime Error

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    from collections import defaultdict
    #nの素因数分解，[[a1,b1],[a2,b2]...]   aがb個,ddで
    def factorization(n):
        flag=0
        if n==1:
            return [0,1]
        dd = 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
                dd[i]=cnt
                flag=1

        if temp!=1:
            dd[temp]=1
            flag=1

        if flag==0:
            dd[n]=1

        return dd
    
    lcm_dd = defaultdict(int)
    
    N=I()
    A=LI()
    L=[]
    for i in range(N):
        a=A[i]
        dd=factorization(a)
        for k,v in dd.items():
            p,cnt=k,v
            lcm_dd[p]=max(lcm_dd[p],cnt)
            
    lcm=1
    for k,v in lcm_dd.items():
        temp=pow(k,v,mod)
        lcm=(lcm*temp)%mod
        
    ans=0
    for i in range(N):
        temp=(lcm*pow(A[i],mod-2,mod))%mod
        ans=ans+temp
        
    print(ans%mod)
        
    


main()

Submission status: Runtime Error

Solution code:
from math import gcd
MOD = 10**9+7

def LCM(n,r):
    return ((n*r) * pow(gcd(n,r), MOD-2,MOD)) % MOD
    
N = int(input())
A = list(map(int,input().split()))
lcm = LCM(A[0],A[1])
for i in range(1,N):
    lcm = LCM(lcm,A[i])

ans = 0
for i in range(N):
    ans += lcm * pow(A[i],MOD-2,MOD)
    ans %= MOD
print(ans)

Submission status: Runtime Error

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

s = A[0]
for i in range(N):
    t = int(A[i] * s / math.gcd(A[i], s))
    s = t

B = []
for i in range(N):
    b = s/A[i]
    B.append(b%(10**9 + 7))

ans = sum(B)%(10**9 + 7)
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

L = list(map(int,input().split()))
R = list(map(int,input().split()))

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common = 1
for i in range(len(A)):
    common = common * a // math.gcd(common, A[i])

ans = 0
for i in range(len(A)):
    ans += common // A[i]
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
def main()
    from math import gcd
    mod = 10**9 +7
    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 = 0
    for a in A:
        ans += (l//a)%mod
        ans %= mod
    print(ans)
main()

Submission status: Runtime Error

Solution code:
import sys
import itertools
import functools
from math import gcd


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


def lcm(x):
    return functools.reduce(lcm2, x)


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))
    a_lcm = lcm(A)

    mod = 10 ** 9 + 7

    ans = 0
    for a in A:
        ans += a_lcm // a
        if ans > mod:
            ans %= mod
            
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
P = 10**9 + 7

import math
import numpy as np

primes = []
check = [True] * (10**3 + 1)
for p in range(2, 10**3):
    if check[p] == True:
        primes.append(p)
        for j in range(2, 10**3 // p + 1):
            check[p * j] = False

def pf(A):
    e = [0] * 10**6
    for p in primes:
        while A % p == 0:
            A = A // p
            e[p] += 1
    
    if A != 1:
        e[A] = 1
        primes.append(A)

    return e

N = int(input())
A = [int(x) for x in input().split()]
E = [pf(A[i]) for i in range(N)]

L = [0] * 10**6
for p in primes:
    L[p] = max(E[i][p] for i in range(N))

F = [[0] * 10**6 for i in range(N)]
for i in range(N):
    for p in primes:
        F[i][p] = L[p] - E[i][p]

ans = 0
for i in range(N):
    B = 1
    for p in primes:
        B = B * p**F[i][p] % P
    
    ans = (ans + B) % P

print(ans)

Submission status: Runtime Error

Solution code:
P = 10**9 + 7

import math
import numpy as np

primes = []
check = [True] * (10**3 + 1)
for p in range(2, 10**3):
    if check[p] == True:
        primes.append(p)
        for j in range(2, 10**3 // p + 1):
            check[p * j] = False

def pf(A):
    e = [0] * 10**3
    for p in primes:
        while A % p == 0:
            A = A // p
            e[p] += 1
    
    if A != 1:
        e[A] = 1

    return e

N = int(input())
A = [int(x) for x in input().split()]
E = [pf(A[i]) for i in range(N)]

L = [0] * 10**3
for p in primes:
    L[p] = max(E[i][p] for i in range(N))
    
F = [[0] * 10**3 for _ in range(N)]
for i in range(N):
    for p in primes:
        F[i][p] = L[p] - E[i][p]

B = [1] * N
for i in range(N):
    for p in primes:
        B[i] = (B[i] * p ** F[i][p]) % P
        
ans = sum(B) % P

print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd

def lcm(X):
    m=(X[0]*X[1])//gcd(X[0],X[1])

    for i in range(2,len(X)):
        g=gcd(m,X[i])
        m=(m*X[i])//g
    return m


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

M=lcm(A)
K=0
for a in A:
    K+=M//a
    K%=Mod
print(K)

Submission status: Runtime Error

Solution code:
import math

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

mod = 10**9+7

primes = [0]*(10**3+1)

def prime_fac(n):
  temp = n
  Flag = True
  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      primes[i] = max(primes[i], cnt)
      Flag = False
  if temp != 1:
    primes[temp] = max(primes[temp], 1)
  if Flag:
    primes[n] = max(primes[n], 1)

for a in A:
  prime_fac(a)

LCM = 1
for p, i in enumerate(primes):
  if i:
    LCM *= pow(p, i, mod)
    LCM %= mod

ans = 0
for a in A:
  ans += LCM * pow(a, mod-2, mod) % mod
  ans %= mod

print(ans)

Submission status: Runtime Error

Solution code:
import math

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

mod = 10**9+7

primes = [0]*(10**3+1)

def prime_fac(n):
  temp = n
  Flag = True
  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      primes[i] = max(primes[i], cnt)
      Flag = False
  if temp != 1:
    primes[temp] = max(primes[temp], 1)
  if Flag:
    primes[n] = max(primes[n], 1)

for a in A:
  prime_fac(a)

LCM = 1
for p, i in enumerate(primes):
  if p:
    LCM *= pow(p, i, mod)
    LCM %= mod

ans = 0
for a in A:
  ans += LCM * pow(a, mod-2, mod) % mod
  ans %= mod

print(ans)

Submission status: Runtime Error

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

mod = 10**9+7
#mod = 11

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

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

print(ans)

Submission status: Runtime Error

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

mod = 10**9+7

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

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

print(ans)

Submission status: Runtime Error

Solution code:
/* 
* ID: juryc
* PROG: Flatten
* LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
const int N = 100+1;
vector<int> primes(N); 
vector<int> num(N,0);
vector<int> pres(N,0);  
ll powmod(ll a,ll b){
ll res=1; a%=mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
} 
ll sieve(){
fill(primes.begin(),primes.end(),1); 
primes[0]=primes[1]=0; 
for(int i=2;i*i<=N;i++){
if(primes[i]){
ll mx=0;
for(int j=i;j<N;j+=i){
primes[j]=0;
if(num[j]){
ll cnt=0; 
while(num[j]%i==0){
cnt++,num[j]/=i;
}
mx=max(mx,cnt); 
}
}
pres[i]=mx;
}
}
}
int main(){
ll n; cin>>n;
vector<ll> v(n);   
for(ll& i : v) {cin>>i; num[i]=i; }
sieve();ll ans=0; for(ll i: v) if(num[i]) pres[num[i]]=1; 
ll lcm=1;
for(int i=1;i<N;i++) if(pres[i]) lcm=(lcm*powmod(i,pres[i]))%mod; 
for(ll i: v){
ans=(ans+(lcm*powmod(i,mod-2))%mod)%mod;
}
cout<<ans<<"\n"; 
return 0;
}

Submission status: Runtime Error

Solution code:
/* 
* ID: juryc
* PROG: Flatten
* LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
const int N = 1e6+1;
vector<int> primes(N); 
vector<int> num(N,0);
vector<int> pres(N,0);  
ll powmod(ll a,ll b){
ll res=1; a%=mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
} 
ll sieve(){
fill(primes.begin(),primes.end(),1); 
primes[0]=primes[1]=0; 
for(int i=2;i*i<=N;i++){
if(primes[i]){
ll mx=0;
for(int j=i;j<N;j+=i){
primes[j]=0;
if(num[j]){
ll cnt=0; 
while(num[j]%i==0){
cnt++,num[j]/=i;
}
mx=max(mx,cnt); 
}
}
pres[i]=mx;
}
}
}
int main(){
ll n; cin>>n;
vector<ll> v(n);   
for(ll& i : v) {cin>>i; num[i]=i; }
sieve();ll ans=0; for(ll i: v) if(num[i]) pres[num[i]]=1; 
ll lcm=1;
for(int i=1;i<N;i++) if(pres[i]) lcm=(lcm*powmod(i,pres[i]))%mod; 
for(ll i: v){
ans=(ans+(lcm*powmod(i,mod-2))%mod)%mod;
}
cout<<ans<<"\n"; 
return 0;
}

Submission status: Runtime Error

Solution code:
/* 
* ID: juryc
* PROG: Flatten
* LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
const int N = 1e6+1;
vector<int> mp(N,0);
vector<int> primes(N); 
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b); 
}
ll powmod(ll a,ll b){
ll res=1; a%=mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
} 
ll sieve(){
ll res=1;
fill(primes.begin(),primes.end(),1); 
primes[0]=primes[1]=0; 
for(int i=2;i<N;i++){
if(primes[i]){
ll mx=0;
for(int j=i;j<N;j+=i){
primes[j]=0;
if(mp[j]){
ll cnt=0; ll tmp=j;
while(tmp%i==0){
cnt++,tmp/=i;
}
mx=max(mx,cnt); 
}
}
res=(res*powmod(i,mx))%mod;
}
}
return res;
}
int main(){
ll n; cin>>n;
vector<ll> v(n); 
for(ll& i : v) {cin>>i; mp[i]=1; }
ll lcm=sieve(),ans=0;
for(ll i: v){
ans=(ans+(lcm*powmod(i,mod-2))%mod)%mod;
}
cout<<ans<<"\n"; 
return 0;
}

Submission status: Runtime Error

Solution code:
/* 
* ID: juryc
* PROG: Flatten
* LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
map<ll,ll> mp; 
ll gcd(ll a,ll b){
if(b==0) return a;
return gcd(b,a%b); 
}
ll powmod(ll a,ll b){
ll res=1; a%=mod;
while(b){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
const int N = 1e6+5;
vector<int> primes(N); 
ll sieve(){
ll res=1;
fill(primes.begin(),primes.end(),1); 
primes[0]=primes[1]=0; 
for(int i=2;i<N;i++){
if(primes[i]){
ll mx=0;
for(int j=i;j<N;j+=i){
primes[j]=0;
if(mp.find(j)!=mp.end()){
ll cnt=0; ll tmp=j;
while(tmp%i==0){
cnt++,tmp/=i;
}
mx=max(mx,cnt); 
}
}
res=(res*powmod(i,mx))%mod;
}
}
return res;
}
int main(){
ll n; cin>>n;
vector<ll> v(n); 
for(ll& i : v) {cin>>i; mp[i]=1; }
ll lcm=sieve(),ans=0;
for(ll i: v){
ans=(ans+(lcm*powmod(i,mod-2))%mod)%mod;
}
cout<<ans<<"\n"; 
return 0;
}

Submission status: Runtime Error

Solution code:
### 素因数分解する。
from collections import defaultdict

def factorize(n):
    """

    """
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i==0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in LCM:
                LCM[i] = max(LCM[i], cnt)
            else:
                LCM[i] = cnt
    if tmp != 1:
        LCM[tmp] = max(LCM[tmp], 1)
    if not LCM:
        LCM[N] = max(LCM[N], 1)

def inv(n, p):
    return pow(n, p-2, p)

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

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

lcm = 1
for key, val in LCM.items():
    lcm *= pow(key, val, mod)
    lcm %= mod

inv_sum = 0
for i in range(N):
    inv_sum += inv(A[i], mod)
    inv_sum %= mod

print(lcm * inv_sum % mod)

Submission status: Runtime Error

Solution code:
from math import sqrt
def main():
    
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    MAX = max(A)
    CONST = int(sqrt(MAX)) + 1000
    LCM = {num: 0 for num in range(2, CONST)}
    A2Factor = [{num: 0 for num in range(2, CONST)} for _ in range(N)]
    for i in range(N):
        A2Factor[i][A[i]] = 0
        LCM[A[i]] = 0

    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):
        ans_dict = dict()
        tmp = 1
        for num in range(2, CONST):
            ans_dict[num] = abs(LCM[num] - A2Factor[i][num])
        ans_dict[A[i]] = abs(LCM[A[i]] - A2Factor[i][A[i]])
        # print(ans_dict)
        for key, value in ans_dict.items():
            tmp *= pow(key, value, p)
            tmp %= p
        ans += tmp % p

    print(ans % p)
main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    MAX = max(A)

    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]]
    PRIME_LIST = primes(MAX)
    LCM = {num: 0 for num in PRIME_LIST}
    A2Factor = [{num: 0 for num in PRIME_LIST} for _ in range(N)]

    def factorization(n, idx):
        temp = n
        flag = 0
        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
                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):
        ans_dict = {}
        tmp = 1
        for num in PRIME_LIST:
            ans_dict[num] = abs(LCM[num] - A2Factor[i][num])
        for key, value in ans_dict.items():
            tmp *= pow(key, value, p)
            tmp %= p
        ans += tmp%p
    print(ans % p)
main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    MAX = max(A)
    LCM = {num: 0 for num in range(2, MAX+1)}
    A2Factor = [{num: 0 for num in range(2, MAX+1)} for _ in range(N)]

    def factorization(n, idx):
        temp = n
        flag = 0
        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
                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):
        ans_dict = {}
        tmp = 1
        for num in range(2, MAX+1):
            ans_dict[num] = abs(LCM[num] - A2Factor[i][num])
        for key, value in ans_dict.items():
            tmp *= pow(key, value, p)
            tmp %= p
        ans += tmp%p
    print(ans % p)
main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    MAX = max(A)
    LCM = {num: 0 for num in range(2, MAX+1)}
    A2Factor = [{num: 0 for num in range(2, MAX+1)} for _ in range(N)]

    def factorization(n, idx):
        temp = n
        flag = 0
        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
                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):
        ans_dict = {}
        tmp = 1
        for num in range(2, MAX+1):
            ans_dict[num] = abs(LCM[num] - A2Factor[i][num])
        for key, value in ans_dict.items():
            tmp *= pow(key, value, p)
            tmp %= p
        ans += tmp%p
    print(ans % p)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
n=int(input())
lista=list(map(int,input().split()))
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 
sum1=0
if(len(lista)>=2):
	num1=lista[0]
	num2=lista[1]
	lcm=find_lcm(num1,num2)
	for i in range(2,n):
		lcm=find_lcm(lcm,lista[i])
	for i in range(n):
		sum1+=lcm/lista[i]
	print(int(sum1))
else:
	print(1)

Submission status: Runtime Error

Solution code:
n=int(input())
lista=list(map(int,input().split()))
def find_lcm(num1, num2): 
    if(num1>num2): 
        num = num1 
        den = num2 
    else: 
        num = num2 
        den = num1 
    rem = num % den 
    while(rem != 0): 
        num = den 
        den = rem 
        rem = num % den 
    gcd = den 
    lcm = int(int(num1 * num2)/int(gcd)) 
    return lcm 
sum1=0
if(len(lista>=2)):
	num1=lista[0]
	num2=lista[1]
	lcm=find_lcm(num1,num2)
	for i in range(2,n):
		lcm=find_lcm(lcm,lista[i])
	for i in range(n):
		sum1+=lcm/lista[i]
	print(sum1)
else:
	print(1)

Submission status: Runtime Error

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: Runtime Error

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
    ans += tmp_value
    ans = ans % mod
print(ans)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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

print(sum(map(lambda x: (l // a) % MOD)))

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
count = [0 for _ in range(a+1)]
count[2] = 1
for k in range(3, a+1, 2):
  if count[k] == 0:
    count[k] = 1
    prime_num.append(k)
    for j in range(k, a+1, k):
      count[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: Runtime Error

Solution code:
inv=[0,1]
mod=10**9+7
for i in range(2,1000001):
  inv.append((m-inv[mod%i]*(m//i))%m)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll m = 1e9 + 7;
ll powm(ll b, ll p)
{
  if (p == 0)
  return 1;
  if (p % 2 == 1)
  return b * powm(b, p - 1) % m;
  else
  {
    ll t = powm(b, p / 2);
    return t * t % m;
  }
}
int main()
{
  int n;
  cin >> n;
  vector<int> a(n);
  map<int, int> flcm;
  vector<map<int, int>> b(n);
  for (int i = 0; i < n; i++)
  cin >> a[i];

  for (int i = 0; i < n; i++)
  {
    int t = a[i];
    for (ll j = 2; j * j <= t; j++)
    {
      while (t % j == 0)
      {
        b[i][j] += 1;
        t /= j;
      }
      if (b[i][j] > flcm[j])
      flcm[j] = b[i][j];
    }
    if (t != 1)
    {
      b[i][t]++;
      if (flcm[t] == 0)
      flcm[t] = 1;
    }
  }
  ll ans = 0;
  ll lcm = 1;
  for (auto x : flcm)
  {
    lcm = lcm * powm(x.first, x.second) % m;
  }
  for (int i = 0; i < n; i++) {
  	ans += lcm * powm(a[i], m - 2) % m;
  }
  cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
so_list = [0 for i in range(10**4)]
mod = 10**9+7

def fac(n):
    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
            if so_list[i]<cnt:
              so_list[i]= cnt
    if temp!=1:
      if so_list[temp]==0:
        so_list[temp]=1
for i in range(n):
  a1 = a[i]
  fac(a1)
l = 1
for i in range(len(so_list)):
  if so_list[i]!=0:
    l *= pow(i,so_list[i],mod)
    l %= mod
ans = 0
#print(l)
for i in a:
  t = pow(i,mod-2,mod)
  ans += (l*t)%mod
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.realdine
mod = int(1e9)+7
n=int(input())
L=list(map(int,input().split()))
M=np.array(L)
x=np.lcm.reduce(M)
ans = 0
for i in L:
    ans+=L[i]//x
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.realdine
mod = int(1e9)+7
n=int(input())
L=list(map(int,input().split()))
M=np.array(L)
x=mp.lcm.reduce(M)
ans = 0
for i in L:
    ans+=L[i]//x
print(ans%mod)

Submission status: Runtime Error

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_all=False):
        assert x >= 2
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0 or return_all:
                result.append((p, exp))
            if p * p > x and return_all is False:
                break
        if x > 1:
            result.append((x, 1))
        return result


N = int(input())
M = 10**9 + 7
A = list(map(int, input().split()))
A = [a for a in A if a >= 2]

sieve = SieveOfEratosthenes(10**3)
F = [sieve.factorize(a, return_all=True) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    lcm = [(p, max(e1, e2)) for (p, e1), (_, e2) in zip(lcm, F[i])]

val = 1
for p, e in lcm:
    val = val * pow(p, e, M) % M

B = [val * pow(a, M - 2, M) % M for a in A]
print(sum(B) % M)

Submission status: Runtime Error

Solution code:
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_all=False):
        assert x >= 2
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0 or return_all:
                result.append((p, exp))
            if p * p > x and return_all is False:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(max(A))
A = [sieve.factorize(a, return_all=True) for a in A if a >= 2]

lcm = A[0]
for i in range(1, len(A)):
    lcm = [(p, max(e1, e2)) for (p, e1), (_, e2) in zip(lcm, A[i])]

ans = 0
for i in range(len(A)):
    items = [(p, e1 - e2) for (p, e1), (_, e2) in zip(lcm, A[i])]
    b = 1
    for p, e in items:
        b = b * pow(p, e, M) % M
    ans = (ans + b) % M
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    #ans = ans + (lcm // v)) % MOD
    ans = ans + (lcm // v)) % MOD
print(ans % MOD)