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 math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.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()))
answer = 0
mod = 10**9 + 7
# print(*A)
# print(lcm(*A))
LCM = lcm(*A)

for i in range(N):
    answer += LCM // A[i]

print(answer % mod)

Submission status: Runtime Error

Solution code:
# import numpy as np
from fractions import math
from functools import reduce

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



def lcm(a, b):
    # return (a * b) // np.gcd(a, b)
    return (a * b) // math.gcd(a, b)

L = reduce(lcm, a)

# print(L)

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

print(ans)

Submission status: Runtime Error

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]

raise Exception
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Runtime Error

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    # 終点はルート切り捨て+1
    for i in range(2, int(sqrt(num))+1):
        # 素因数分解：小さい方から割れるだけ割って素数をカウント
        while num % i == 0:
            num //= i
            d[i] += 1
        # 1まで分解したら終了
        if num == 1:
            break
    # 最後に残ったnumは素数(ただし1^1は1^0なので数に入れない)
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    return C1 & C2

def lcm(C1, C2):
    return C1 | C2

N = INT()
A = LIST()

# 素因数の状態で全体のLCMを出す
A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)

raise Exception

# 通常の値に戻す
l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd #直して
n = int(input())
a = list(map(int, input().split()))
def primelist(N):
    prime = [2]
    for i in range(3, N+1):
        flag = 1
        for j in prime:
            if i % j == 0:
                flag = 0
                break
        if flag == 1:
            prime.append(i)
    return prime
prime = primelist(1001)

def factorization(n):
    arr = []
    temp = n
    for i in prime:
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

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

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

    return arr


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

fact = [0] * (1000001)
pri = []
for i in range(n):
    f = factorization(a[i])
    for fac, c in f:
        fact[fac] = max(fact[fac], c)

fact_list = []
for i in range(1000001):
    if fact[i] > 0:
        fact_list.append((i, fact[i]))



"""
ans = 0
for i in range(n):
    m = modinv(a[i])
    for fac, c in fact_list:
        m *= pow(fac, c, mod)
        m %= mod

    ans += m
    ans %= mod
"""
print(ans)

Submission status: Runtime Error

Solution code:
m 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 gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
n = int(input())
A = list(map(int, input().split()))
k = lcm_list(A)
r = 0
ln = list(range(n))
for i in ln:
    r += k//A[i]
print(r%(10**9+7))

Submission status: Runtime Error

Solution code:
from fractions import gcd

def lcm(c,d):
    return c//gcd(c,d)*d
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    #ans%=mod
print(ans%=mod)

Submission status: Runtime Error

Solution code:
import gcd from fractions

def lcm(a,b):
    return a//gcd(a)*b
mod=10**9+7
n=int(input())
a=[int(i) for i in input().split()]
l=a[0]
for i in range(1,n):
    l=lcm(l,a[i])
ans=0
for i in range(n):
    ans+=l//a[i]
    ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
a = list(map(int, input().split()))

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // math.gcd(lcm, a[i])
#------------------------------------------
ans =0


for j in a:
    ans += lcm // j
ans %= 1000000007
print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
a = list(map(int, input().split()))

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // math.gcd(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0


for j in range(len(b)):
    ans +=b[j]%1000000007



print(ans)

Submission status: Runtime Error

Solution code:
import math
N=int(input())
a = list(map(int, input().split()))

#------------最小公倍数---------------------
lcm = a[0]
for i in range(1, N):
    lcm = lcm * a[i] // math.gcd(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0


for j in range(len(b)):
    ans +=b[j]

ans%=1000000007

print(ans)

Submission status: Runtime Error

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

#------------最小公倍数---------------------
lcm = 1
for i in range(1, N):
    lmc = lcm * a[i] // fractions.lcm(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0

for j in b:
    ans +=(lcm// b[j])%1000000007


print(ans)

Submission status: Runtime Error

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

#------------最小公倍数---------------------
lcm = 1
for i in range(1, N):
    lmc = lcm * a[i] // fractions.lcm(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0

for j in b:
    ans +=(lcm// b)%1000000007


print(ans)

Submission status: Runtime Error

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

#------------最小公倍数---------------------
lcm = 1
for i in range(1, N):
    lmc = lcm * a[i] // fractions.lcm(lcm, a[i])
#------------------------------------------
b= []
for i in range(N):
    b.append(lcm //a[i])
ans=0

for j in b:
    ans +=lcm// b
    ans%=1000000007


print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(N):
    lcm = lcm * a[i] // gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(lcm//aa)%(10**9+7))

Submission status: Runtime Error

Solution code:
from fractions import gcd
N=int(input())
a = list(map(int, input().split()))
lcm = 1
for i in range(N):
    lcm = lcm * a[i] // gcd(ans, a[i])
import numpy as np
aa = np.array(a)
print(sum(ans//aa)%(10**9+7))

Submission status: Runtime Error

Solution code:
from fractions import gcd
from functools import reduce

lcm = lambda a, b: b // lcm(a, b) * a
mod = 10 ** 9 + 7

N, *A = map(int, open(0).read().split())

L = reduce(lcm, A) % mod
print(sum(L * pow(a, mod - 2, mod) % mod for a in A) % mod)

Submission status: Runtime Error

Solution code:
import math

def Lcm(a , b):
	return (a * b)//math.gcd(a,b)

n = int(input())
a = [int(x) for x in input().split(" ")]
lcm = 1; num = 0;
for i in range(n):
	lcm = Lcm(lcm , a[i])
for i in range(n):
	val = lcm//a[i];
	num = (num + val)
num = num // math.gcd(lcm,num)
num = (num % 1000000007)
print(num)

Submission status: Runtime Error

Solution code:
import math

def Lcm(a , b):
	return (a * b)//math.gcd(a,b)

def main():
	n = int(input())
	a = [int(x) for x in input().split(" ")]
	lcm = 1; num = 0;
	for i in range(n):
		lcm = Lcm(lcm , a[i])
	for i in range(n):
		val = lcm//a[i];
		num = (num + val)
	num = num // math.gcd(lcm,num)
	num = (num % 1000000007)
	print(num)

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 5
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 5):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 5, p):
                p_candidate_list[q] = 0
    primes_1000000 = [p for p in range(1000000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    # assert solve(5, [12, 12, 12, 12, 12]) == 5
    # assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
l = [0]*(max(A)+1)
for a in A:
  x=0
  while a%2==0:
    a//=2
    x+=1
    
  l[2]=max(l[2],x)
  
  f = 3
  while f**2<=a:
    x = 0
    while a%f==0:
      a//=f
      x+=1
    l[f]=max(l[f],x)
    f+=2
    
  if a!=1:
    l[a]=max(l[a],1)
    
b = 1
for i,x in enumerate(l):
  b*=pow(i,x,mod)
  b%=mod
  
ans = 0
for a in A:
  ans+=(b*pow(a,mod-2,mod))%mod
  ans%=mod
  
print(ans%mod)

Submission status: Runtime Error

Solution code:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
const ll MAX = 11000000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n) {//a^n(MOD)を求める
    long long res = 1;
    while (n > 0) {
         if (n & 1) res = res * a % MOD;
         a= a * a % MOD;//次の準備
         n >>= 1;
      }
 return res;
}

// a/b(mod p)
ll waru(ll a,ll b){
    return a*modpow(b,MOD-2)%MOD;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;cin>>n;
    ll ans=0,x=1;
    COMinit();
    vector<ll>a(n);
    map<ll,ll>m;
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        ll now=a[i];
        for(ll j=2;j*j<=now;j++){
            ll cnt=0;
            while(now%j==0){
                cnt++;
                now/=j;
            }
            if(cnt)chmax(m[j],cnt);
        }
        if(now!=1)chmax(m[now],1);
    }
    for(auto now:m){
        x*=modpow(now.fi,now.se);
        x%=MOD;
    }
    for(int i=0;i<n;i++){
        ans+=waru(x,a[i]);
        ans%=MOD;
    }
    cout << ans << endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

Submission status: Runtime Error

Solution code:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
const ll MAX = 11000000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n) {//a^n(MOD)を求める
    long long res = 1;
    while (n > 0) {
         if (n & 1) res = res * a % MOD;
         a= a * a % MOD;//次の準備
         n >>= 1;
      }
 return res;
}

// a/b(mod p)
ll waru(ll a,ll b){
    return a*modpow(b,MOD-2)%MOD;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;cin>>n;
    ll ans=0,x=1;
    COMinit();
    vector<ll>a(n);
    map<ll,ll>m;
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        ll now=a[i];
        for(ll j=2;j*j<=now;j++){
            ll cnt=0;
            while(now%j==0){
                cnt++;
                now/=j;
            }
            if(cnt)chmax(m[j],cnt);
        }
        if(now!=1)chmax(m[now],1);
    }
    for(auto now:m){
        x*=modpow(now.fi,now.se);
        x%=MOD;
    }
    for(int i=0;i<n;i++){
        ans+=x*inv[a[i]]%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

Submission status: Runtime Error

Solution code:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
const ll MAX = 1100000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n) {//a^n(MOD)を求める
    long long res = 1;
    while (n > 0) {
         if (n & 1) res = res * a % MOD;
         a= a * a % MOD;//次の準備
         n >>= 1;
      }
 return res;
}

// a/b(mod p)
ll waru(ll a,ll b){
    return a*modpow(b,MOD-2)%MOD;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;cin>>n;
    ll ans=0,x=1;
    COMinit();
    vector<ll>a(n);
    map<ll,ll>m;
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        ll now=a[i];
        for(ll j=2;j*j<=now;j++){
            ll cnt=0;
            while(now%j==0){
                cnt++;
                now/=j;
            }
            if(cnt)chmax(m[j],cnt);
        }
        if(now!=1)chmax(m[now],1);
    }
    for(auto now:m){
        x*=modpow(now.fi,now.se);
        x%=MOD;
    }
    for(int i=0;i<n;i++){
        ans+=x*inv[a[i]]%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

Submission status: Runtime Error

Solution code:
//  Created by conan1024hao in 2019.
//  Copyright © 2019 conan1024hao. All rights reserved.
//  専用ライブラリです、自由にコピーして構いません。
//  感谢看我的代码！Wechat:conan1024hao Twitter/QQ:810396815
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10e16
#define MOD 1000000007
#define mod 1000000007
#define rep(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
//using Int=int_fast64_t;
typedef long long int ll;
typedef long long int LL;
typedef pair<ll,ll>Pll;
typedef pair<int,int>Pin;
long long GCD(long long a, long long b) { return b ? GCD(b, a%b) : a; }
long long LCM(long long a, long long b)  {return a/GCD(a,b)*b;}
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};
char dir[4]={'u','l','d','r'};
ll cmp1(pair<ll,string>a,pair<ll,string> b){
        if(a.fi!=b.fi)
        return a.fi<b.fi;
        else
        return a.se<b.se;
}

//---------------------------------------------------------------------------
const int MAX = 1100000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long modpow(long long a, long long n) {//a^n(MOD)を求める
    long long res = 1;
    while (n > 0) {
         if (n & 1) res = res * a % MOD;
         a= a * a % MOD;//次の準備
         n >>= 1;
      }
 return res;
}

// a/b(mod p)
ll waru(ll a,ll b){
    return a*modpow(b,MOD-2)%MOD;
}
//---------------------------------------------------------------------------
int main(){//問題をちゃんと見ろ!!!!!!!!!!!!!!!!!      llか??????????统一类型        memset()!!!!!!!!!!!!       ペナを減らせ!!!!!!!!!!!!!
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------
    ll n;cin>>n;
    ll ans=0,x=1;
    COMinit();
    vector<ll>a(n);
    map<ll,ll>m;
    for(ll i=0;i<n;i++)cin>>a[i];
    for(ll i=0;i<n;i++){
        ll now=a[i];
        for(ll j=2;j*j<=now;j++){
            ll cnt=0;
            while(now%j==0){
                cnt++;
                now/=j;
            }
            if(cnt)m[j]=max(cnt,m[j]);
        }
        if(now!=1)chmax(m[now],1);
    }
    for(auto now:m){
        x*=modpow(now.fi,now.se);
        x%=MOD;
    }
    for(int i=0;i<n;i++){
        ans+=x*inv[a[i]]%MOD;
        ans%=MOD;
    }
    cout << ans << endl;
    //-------------------------------
    return 0;
}
//---------------------------------------------------------------------------

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import math

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

MOD = 10 ** 9 + 7

primes = defaultdict(int)

for a in A:
    x = a
    p = 2
    for p in range(2, int(math.sqrt(a)) + 1):
        cnt = 0
        while x % p == 0:
            x //= p
            cnt += 1
        primes[p] = max(primes[p], cnt)
    if x > 1:
        primes[x] = max(primes[x], 1)

l = 1
for p in primes:
    l = (l * pow(p, primes[p], MOD)) % MOD

res = 0
for a in A:
    res = (res + (l * pow(a, MOD - 2, MOD) % MOD) % MOD

print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import Counter

def resolve():
    # 方針
    # LCMを求めたい
    #  Aを素因数分解して、素因数ごとに肩のmaxを取りに行く
    #  max同士を掛け合わせる
    # B = X / A : 逆元
    #  B = A^(p-2) , p: 素数 prime

    # たくさんの数の素因数分解
    #     (1こだけの場合。Xに対し、sqrt(X)まで順に見て割り切れなければ素数として判定)
    #  (1) 素数列挙
    #    エラトステネスの篩
    #     素数と決まった数の倍数を消していく(最初は2)
    #     次の数にいく。消されてなければ素数。その数の倍数を消していく。(2乗となる倍数から開始すれば良い)　-> O(NloglogN)
    #     
    #  (2) 素因数分解
    #     上記の操作の時、何で割られたかメモしていく。すでに書かれているものは上書きしない。
    #     例:36. 36 ->2-> 18 ->2-> 9 ->3-> 3(prime) = 2x2x3x3 (sorted)
    #    => 素因数分解の完了
    # 
    MOD = 10**9 + 7
    N = int(input())
    A = list(map(int, input().split()))

    # 素数列挙 & 割った数の計算
    MX = int(10**6)
    L = np.zeros(MX+1)
    L[0] = -1
    L[1] = -1
    primes = []

    for i in range(2, MX+1):
        if L[i]:
            continue
        primes.append(i)
        L[i] = i
        for j in range(i*i, MX+1, i):
            if L[j] == 0:
                L[j] = i

    def factor(x: int):
        res = []
        while x != 1:
            prime = L[x] if L[x] != 0 else x
            res.append(prime)
            x /= prime
        return res

    max_e = {}
    for a in A:
        a = Counter(factor(a))
        for key, v in a.items():
            if not key in max_e:
                max_e[key] = v
            else:
                if v > max_e[key]:
                    max_e[key] = v
    # print(max_e)

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

    lcm = 1
    for key, v in max_e.items():
        lcm *= key ** v

    # print(max_e)
    # print(lcm)
    lcm %= MOD
    # print(lcm)

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

    print(int(ans % MOD))

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

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)
ans = 0
for i in A:
	ans += l/i

MOD = 1000000007
print(int(ans%MOD))

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

# from functools import reduce
# from math import gcd as gcd_base  # from fractions import gcd
# gcd = lambda *numbers: reduce(gcd_base, numbers)  # 3 数以上の最大公約数

# lcm_base = lambda x, y: (x * y) // gcd_base(x, y)
# lcm = lambda *numbers: reduce(lcm_base, numbers, 1)  # 3 数以上の最小公倍数
# 最小公倍数
# def gcd(a, b):
#     if a < b:
#         a, b = b, a
#     while a % b != 0:
#         a, b = b, a % b
#     return b


## 最大公約数 
def lcm(a, b):
    y = a*b / gcd(a, b)
    return int(y)

def many_lcm(l):
    for i in range(len(l)-1):
        if i == 0:
            ans = lcm(l[0], l[1])
        else:
            ans = lcm(l[i+1], ans)
    return ans
N = INT()
A = LIST()

lm = many_lcm(A)
# print(l)
B = []
for a in A:
    B.append(lm // a)
print(sum(B) % mod)

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
import math
for i in a:
    t*=i//math.gcd(t,i)
print(sum(t//i for i in a)%mod)