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: Accepted

Solution code:
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def mul(a, b):
    return (a * b) % mod
    
def my_pow(a, b):
    if b == 0:
        return 1
    elif b % 2 == 1:
        return mul(a, my_pow(a, b-1))
    else:
        temp = my_pow(a, b/2)
        return mul(temp, temp)

def my_inv(a):
    return my_pow(a, mod-2)

def modInverse(a, m) : 
    m0 = m 
    y = 0
    x = 1
  
    if (m == 1) : 
        return 0
  
    while (a > 1) : 
  
        # q is quotient 
        q = a // m 
  
        t = m 
  
        # m is remainder now, process 
        # same as Euclid's algo 
        m = a % m 
        a = t 
        t = y 
  
        # Update x and y 
        y = x - q * y 
        x = t 
  
  
    # Make x positive 
    if (x < 0) : 
        x = x + m0 
  
    return x 
  

def main():
    n = int(raw_input())
    
    arr = [int(x) for x in raw_input().split()]
    
    answer = {}
    
    for i in range(n):
        cnt = {}
        
        x = arr[i]
        
        i = 2
        
        while i * i <= x:
            while x % i == 0:
                x /= i
                cnt[i] = cnt.get(i, 0) + 1 
            i += 1
        
        if x != 1:
            cnt[x] = cnt.get(x, 0) + 1
        
        for key in cnt:
            answer[key] = max(answer.get(key, 0), cnt[key])
    
    lcm = 1
    
    for prime in answer:
        for _ in range(answer[prime]):
            lcm = mul(lcm, prime)
    #print(lcm)
    ans = 0
    
    #print(my_pow(22, 3))
    
    for x in arr:
        #print(my_inv(x))
        ans = add(ans, mul(lcm, my_inv(x)))
    
    ans = int(ans)
    
    print(ans)
        
    
main()

"""
#include <bits/stdc++.h>
using namespace std;

using ll = long long; 
const int MOD = 1e9+7;

ll add(ll a, ll b) {
    return (a + b) % MOD;    
}

ll divi(ll a, ll b) {
    return (a / b) % MOD;
}

ll mul(ll a, ll b) {
    return (a * b) % MOD;
}

// Return a ^ b 
int my_pow(int a, int b) {
    if (b == 0) {
        return 1;
    }
    else if (b % 2 == 1) {
        return mul(a, my_pow(a, b-1));
    }
    else {
        int temp = my_pow(a, b/2);
        return mul(temp, temp);
    }
}

int my_inv(int a) {
    return my_pow(a, MOD-2);
}

int main() {
    int n;
    
    scanf("%d", &n);
    
    vector<int> arr(n);
    
    map<int, int> answer;
    //cout << "test" << endl;
    for (int i = 0; i < n; i++) {
        map<int, int> cnt;        
        scanf("%d", &arr[i]);
        int x = arr[i];
        
        //cout << x << endl;
        
        for (int i = 2; i * i <= x; i++) {
            while (x % i == 0) {
                cnt[i] += 1;
                x /= i;
            }
        }
        
        if (x != 1) {
            cnt[x] += 1;
        }
        
        //cout << "test_x" << endl;
        
        for (pair<int, int> p : cnt) {
            answer[p.first] = max(answer[p.first], p.second);
        }
    }
    //cout << "test2" << endl;
    
    ll lcm = 1;
    for (pair<int, int> p : answer) {
        int prime = p.first;
        int k = p.second;
        for (int i = 0; i < k; i++) {
            lcm = mul(lcm, prime);
        }
    }
    
    ll ans = 0;
    
    //cout << "test1" << endl;
    
    for (int i = 0; i < n; i++) {
        ans = add(ans, mul(lcm, my_inv(arr[i])));
    }
    
    //cout << "test2" << endl;
    
    printf("%lld", ans);
	
	return 0;
}
"""

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


class Factorize(object):

    def __init__(self, maxnum):
        self.primes = self.__smallest_prime_factors(maxnum)

    # 素因数分解する(リスト)
    def factorize_list(self, n):

        fct = []
        while n != 1:
            fct.append(self.primes[n])
            n //= self.primes[n]
        return fct

    # 素因数分解する(辞書)
    def factorize_dict(self, n):
        fct = defaultdict(lambda: 0)
        while n != 1:
            fct[self.primes[n]] += 1
            n //= self.primes[n]
        return fct

    # n以下の最小の素因数を列挙する
    def __smallest_prime_factors(self, n):

        prime = list(range(n + 1))

        for i in range(2, int(n**0.5) + 1):
            if prime[i] != i:
                continue
            for j in range(i * 2, n + 1, i):
                prime[j] = min(prime[j], i)
        return prime


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


def solve():

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

    lcm_dict = defaultdict(lambda: 0)
    for i in range(N):
        d = fct.factorize_dict(A[i])
        for k, v in d.items():
            lcm_dict[k] = max(lcm_dict[k], v)

    lcm = 1
    for k, v in lcm_dict.items():
        lcm *= (k**v)
        lcm %= mod

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

    ans *= lcm
    ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def factorize(n):
    b = 2
    fct = defaultdict(lambda: 0)
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct[b] += 1
        b = b + 1
    if n > 1:
        fct[n] += 1
    return fct


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


def solve():

    N = int(input())
    A = list(map(int, input().split()))
    B = [[1] for _ in range(N)]

    fac_list = defaultdict(lambda: 0)
    for i in range(N):
        d = factorize(A[i])
        for k, v in d.items():
            fac_list[k] = max(fac_list[k], v)

    lcm = 1
    for k, v in fac_list.items():
        lcm *= (k**v)
        lcm %= mod

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

    ans *= lcm
    ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
input = lambda: sys.stdin.readline().rstrip()

mod = 10**9 + 7


def factorize(n):
    b = 2
    fct = dict()
    while b * b <= n:
        while n % b == 0:
            n //= b
            if b in fct:
                fct[b] += 1
            else:
                fct[b] = 1
        b = b + 1
    if n > 1:
        if b in fct:
            fct[n] += 1
        else:
            fct[n] = 1
    return fct


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


def solve():

    N = int(input())
    A = list(map(int, input().split()))
    B = [[1] for _ in range(N)]

    fac_list = dict()
    for i in range(N):
        d = factorize(A[i])
        for k, v in d.items():
            fac_list[k] = max(fac_list.get(k, 0), v)

    lcm = 1
    for k, v in fac_list.items():
        lcm *= (k**v)
        lcm %= mod

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

    ans *= lcm
    ans %= mod
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:

from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a_lcm,a)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:

from fractions import gcd
def main():

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

    MOD = 10**9 + 7

    a_lcm = a_list[0]
    for a in a_list[1:]:
        a_lcm *= a // gcd(a,a_lcm)

    res = 0
    for a in a_list:
        res += a_lcm // a
    print(res%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
from collections import deque

inf = 10**18
mod = 10**9+7

dic = {}

# mod で割り算(フェルマー、逆元利用)
mod = 10**9+7

N = 10**6+1
inv_t = [0]+[1]

for i in range(2,N):
    inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

def moddiv(a, b):
    return a*inv_t[b]%mod

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""
def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    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.append([i, cnt])

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

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

    return arr

n = int(input())
a = list(map(int, input().split()))
j = []
for num in a:
    tmp = factorization(num)
    j.append(tmp)
    for p,x in tmp:
        if p in dic:
            dic[p] = max(dic[p],x)
        else:
            dic[p] = x
gc = 1
for k,v in dic.items():
    gc*=(k**v)%mod
ans = 0
for num in a:
    ans += moddiv(gc, num)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict,Counter
import copy

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

dic = defaultdict(int)

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

for i in a:
    c = Counter(prime_factorize(i))
    for j,k in c.items():
        if dic[j] < k:
            dic[j] = k

l = 1

for i,j in dic.items():
    l *= pow(i,j,mod)
    l %= mod

point = 0

for i in a:
    point += l*pow(i,mod-2,mod)
    point %= mod

print(point%mod)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
from collections import defaultdict,Counter
import copy

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

dic = defaultdict(int)

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

for i in a:
    c = Counter(prime_factorize(i))
    for j,k in c.items():
        if dic[j] < k:
            dic[j] = k

l = 1

for i,j in dic.items():
    l *= pow(i,j,mod)

point = 0

for i in a:
    point += l*pow(i,mod-2,mod)
    point %= mod

print(point%mod)

Submission status: Accepted

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

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

mod = int(1e9+7)
def ext_gcd(a, b, x, y):
    if b==0:
        x[0] = 1
        y[0] = 0
        return a
    g = ext_gcd(b, a%b, y, x)
    y[0]-=a//b*x[0]
    return g

def mod_inv(a):
    x = [0]
    y = [0]
    ext_gcd(a, mod, x, y)
    return (x[0]%mod + mod)%mod;

n = int(input())
vs = list(map(int, input().split()))
l = 1
for x in vs:
    l = lcm(l, x)
l = l%mod;
ans = 0
for x in vs:
    ans = (ans + ((l*mod_inv(x))%mod))%mod
print(ans)

Submission status: Accepted

Solution code:
import fractions
N=int(input())
A=list(map(int,input().split()))
MOD=10**9+7
ans=1
gcd=A[0]
for i in range(1,N):
    a=A[i]
    b=fractions.gcd(a,gcd)
    temp=gcd
    gcd=temp*a//b
    ans=ans*(a//b)+temp//b
    ans%=MOD
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
mod = 10**9 + 7
n, *A = map(int, open(0).read().split())
if len(A) == 1:
    print(1)
else:
    l = reduce(lambda x, y: x*y // gcd(x, y), A) % mod
    s = 0
    for a in A:
        s += l * pow(a, mod-2, mod)
        s %= mod
    print(s)

Submission status: Accepted

Solution code:
from functools import reduce
def reduce_wrapper(func, *args):
    if len(args) == 1:
        return reduce(func, args[0])
    return reduce(func, args)

from fractions import gcd
def lcm(*args):
    return reduce_wrapper(lambda x, y: x*y // gcd(x, y), *args)

def xgcd(a, b):
    ''' return (g, x, y) such that a*x + b*y = g = gcd(a, b) '''
    x0, x1, y0, y1 = 0, 1, 1, 0
    while a != 0:
        (q, a), b = divmod(b, a), a
        y0, y1 = y1, y0 - q * y1
        x0, x1 = x1, x0 - q * x1
    return b, x0, y0

def modinv(n):
    g, x, _ = xgcd(n, mod)
    if g != 1:
        raise ValueError('Modinv is not exist! arg={}'.format(n))
    return x % mod

mod = 10**9 + 7
n, *A = map(int, open(0).read().split())

l = lcm(A) % mod
s = 0
for a in A:
    s += l * modinv(a)
    s %= mod
print(s)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
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
d={2:0}
import collections
for y in l:
  c = collections.Counter(prime_factorize(y))
  for x in c:
    if x in d:
      d[x]=max(d[x],c[x])
    else:
      d[x]=c[x]
mod=10**9+7
gc=1
for x in d:
  gc*=(x**d[x])%mod
ans=0
inv=[1]*1000002
for i in range(2,1000002):
  inv[i]=mod-(inv[mod%i]*(mod//i))%mod
for x in l:
  ans+=gc*inv[x]%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def factorization(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            cnt = 0
            while n % i == 0:
                cnt += 1
                n //= i
            e[i] = max(e[i], cnt)

    if n != 1:
        e[n] = max(e[n], 1)


def mod_pow(a, n):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res


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

mod = 10 ** 9 + 7
e = [0] * 10 ** 6

for v in a:
    factorization(v)

lcm = 1
for i, c in enumerate(e):
    if c > 0:
        lcm = lcm * mod_pow(i, c) % mod

res = 0
for v in a:
    res = (res + lcm * mod_pow(v, mod - 2)) % mod

print(res)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        inv[i] = mod - inv[mod%i] * (mod // i) % mod

initNCMMod(10**6+1)

def integer_factorization(n):
    prime_count = collections.Counter()
    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n //= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1
    return prime_count

def modpow(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x % mod
        x = x*x % mod
        n = n >> 1
    return ans % mod

def main():
    N = I()
    A = LI()
    kobaisu = collections.defaultdict(int)
    div = [1] * N
    for i, a in enumerate(A):
        d = integer_factorization(a)
        for k, v in d.items():
            kobaisu[k] = max(kobaisu[k], v)
            div[i] *= modpow(k, v)
            div[i] %= mod

    kobai = 1
    for k, v in kobaisu.items():
        kobai *= modpow(k, v)
        kobai %= mod

    ans = 0
    for d in div:
        ans += kobai * inv[d] % mod
        ans %= mod
    print(ans)
main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解 前処理O(nloglogn)素因数分解O(logn)
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        fact_dict=dict()
        while x!=1:
            p=self.f[x]
            fact_dict[p]=fact_dict.get(p,0)+1
            x//=self.f[x]
        return fact_dict
class Sieve2: #√nまでの素因数で試し割り 前処理O(√nloglogn+√n/logn)
    def __init__(self,n):
        self.primes=[]
        self.f=[0]*(int(n**0.5)+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,int(n**0.5)+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,int(n**0.5)+1,i):
                if not self.f[j]:
                    self.f[j]=i  #最小の素因数を代入
    def prime_fact(self,x): #素因数分解 {2:p,3:q,5:r,...}
        fact_dict=dict()
        for p in self.primes:
            if p*p>x:break
            while x%p==0:
                x//=p
                fact_dict[p]=fact_dict.get(p,0)+1
        if x>1:fact_dict[x]=fact_dict.get(x,0)+1
        return fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    Prime=Sieve2(10**6+5)
    for a in A:
        f=Prime.prime_fact(a)
        for key in f:
            p_lis[key]=max(p_lis.get(key,0),f[key])
    lcm=1
    for key in p_lis:
        lcm=(lcm*pow(key,p_lis[key],mod))%mod
    ans=0
    for a in A:
        b=lcm*pow(a,mod-2,mod)%mod
        ans=(ans+b)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(N):
    N += 1
    sieve = list(range(N))
    for p in range(2, int(N ** 0.5) + 1):
        if sieve[p] == p:
            for i in range(p << 1, N, p):
                sieve[i] = p
    return sieve

def lcm_with_sieve(numbers, N):
    sieve = sieve_of_eratosthenes(N)
    lcm = dict()
    for n in numbers:
        d = dict()
        while n > 1:
            factor = sieve[n]
            n //= factor
            d[factor] = d.get(factor, 0) + 1
        for factor, power in d.items():
            lcm[factor] = max(lcm.get(factor, 0), power)
    return lcm

MOD = 10 ** 9 + 7
input()
A = tuple(map(int, input().split()))
lcm = 1
for factor, power in lcm_with_sieve(A, 10 ** 6).items():
    lcm = lcm * pow(factor, power, MOD) % MOD
total = 0
for a in A:
    total = (total + lcm * pow(a, MOD - 2, MOD)) % MOD
print(total)

Submission status: Accepted

Solution code:
def sieve_of_eratosthenes(N):
    N += 1
    sieve = [0] * N
    for p in range(2, N):
        if sieve[p]:
            continue
        for i in range(p, N, p):
            sieve[i] = p
    return sieve

def lcm_with_sieve(numbers, N):
    sieve = sieve_of_eratosthenes(N)
    lcm = dict()
    for n in numbers:
        d = dict()
        while n > 1:
            factor = sieve[n]
            n //= factor
            d[factor] = d.get(factor, 0) + 1
        for factor, power in d.items():
            lcm[factor] = max(lcm.get(factor, 0), power)
    return lcm

def main():
    MOD = 10 ** 9 + 7
    _, *A = map(int, open(0).read().split())
    lcm = 1
    for factor, power in lcm_with_sieve(A, 10 ** 6).items():
        lcm = lcm * pow(factor, power, MOD) % MOD
    total = 0
    for a in A:
        total = (total + lcm * pow(a, MOD - 2, MOD)) % MOD
    print(total)

main()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def sieve_of_eratosthenes(N):
    N += 1
    sieve = [0] * N
    for p in range(2, N):
        if sieve[p]:
            continue
        for i in range(p, N, p):
            sieve[i] = p
    return sieve

def lcm_with_sieve(numbers, N):
    sieve = sieve_of_eratosthenes(N)
    lcm = dict()
    for n in numbers:
        d = dict()
        while n > 1:
            factor = sieve[n]
            n //= factor
            d[factor] = d.get(factor, 0) + 1
        for factor, power in d.items():
            lcm[factor] = max(lcm.get(factor, 0), power)
    return lcm

_, *A = map(int, open(0).read().split())
lcm = 1
for factor, power in lcm_with_sieve(A, 10 ** 6).items():
    lcm = lcm * pow(factor, power, MOD) % MOD
total = 0
for a in A:
    total = (total + lcm * pow(a, MOD - 2, MOD)) % MOD
print(total)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
def sieve_of_eratosthenes(N):
    sieve = [0] * (N + 1)
    for p in range(2, N + 1):
        if sieve[p]:
            continue
        for i in range(p, N + 1, p):
            sieve[i] = p
    return sieve

def lcm_with_sieve(numbers, N):
    sieve = sieve_of_eratosthenes(N)
    lcm = dict()
    for n in numbers:
        d = dict()
        while n > 1:
            factor = sieve[n]
            n //= factor
            d[factor] = d.get(factor, 0) + 1
        for factor, power in d.items():
            lcm[factor] = max(lcm.get(factor, 0), power)
    return lcm

input()
A = tuple(map(int, input().split()))
lcm = 1
for factor, power in lcm_with_sieve(A, 10 ** 6).items():
    lcm = lcm * pow(factor, power, MOD) % MOD
total = 0
for a in A:
    total = (total + lcm * pow(a, MOD - 2, MOD)) % MOD
print(total)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

def factorization(n):
    arr = []
    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.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    ans = 0
    for a in al:
        ans += lcm//a
        # if ans >= MOD: ans%=MOD
    ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

def factorization(n):
    arr = []
    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.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    # ans = sum( [ lcm//a for a in al] ) % MOD
    ans = 0
    for a in al:
        ans += lcm//a
        # ans%=MOD
    ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter, defaultdict

input = sys.stdin.readline
MOD = (10**9+7)

def factorization(n):
    arr = []
    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.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr


def pow_k1(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x


def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
        x%=MOD
    return K * x


def main():
    n = int(input())
    al = list(map(int, input().split())) 
    lcm_dic = defaultdict(int)
    # lcm_dic = {}
    # al_facs = []
    for a in al:
        fac = factorization(a)
        # a_fac_dic = {}
        for f in fac:
            # lcm_dic.setdefault(f[0],0)
            lcm_dic[f[0]] = max(f[1], lcm_dic[f[0]])
            # a_fac_dic[f[0]] = f[1]
        # al_facs.append(a_fac_dic)


    lcm = 1
    for prime, cnt in lcm_dic.items():
        lcm *= pow_k1(prime,cnt)

    
    ans = sum( [ lcm//a for a in al] ) % MOD
    # ans = 0
    # for a in al:
    #     ans += lcm//a
    #     ans%=MOD


    # ans = 0
    # for al_f in al_facs:
    #     curr_val = 1
    #     for prime, cnt in lcm_dic.items():
    #         if prime in al_f:
    #             curr_val *= pow_k(prime,(cnt-al_f[prime]))
    #             curr_val%=MOD
    #         else:
    #             curr_val *= pow_k(prime,cnt)
    #             curr_val%=MOD
    #     ans += curr_val
    #     ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
class Sieve: #区間[2,n]の値の素因数分解
    def __init__(self,n=1):
        self.primes=[]
        self.f=[0]*(n+1) #ふるい（素数ならその値）
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1): #素数リスト作成
            if self.f[i]: continue
            self.primes.append(i)
            self.f[i]=i
            for j in range(i*i,n+1,i):
                if not self.f[j]:
                    self.f[j]=i  # 最小の素因数を代入
    def is_prime(self, x):
        return self.f[x]==x
    def prime_fact(self,x): # 素因数分解の昇順リスト, {2:p,3:q,5:r,...}
        fact_dict=dict()
        while x!=1:
            p=self.f[x]
            fact_dict[p]=fact_dict.get(p,0)+1
            x//=self.f[x]
        return fact_dict

def main():
    n=int(input())
    A=list(map(int,input().split()))
    mod=10**9+7
    p_lis={}
    Prime=Sieve(10**6+5)
    for a in A:
        f=Prime.prime_fact(a)
        #print(f)
        for key in f:
            p_lis[key]=max(p_lis.get(key,0),f[key])
    lcm=1
    #print(p_lis)
    for key in p_lis:
        lcm=(lcm*pow(key,p_lis[key],mod))%mod
    ans=0
    #print(lcm)
    for a in A:
        b=lcm*pow(a,mod-2,mod)%mod
        ans=(ans+b)%mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
from functools import reduce

divisor = 10**9 + 7

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

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

N = int(input())
numbers = [int(i) for i in input().split()]

lowest_common_multiple = lcm_list(numbers)

cnt = 0
for i in numbers:
    cnt += lowest_common_multiple // i
    
print(cnt%divisor)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

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

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

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]

print(ans%mod)

Submission status: Accepted

Solution code:
import sys
import fractions

sys.setrecursionlimit(10000000)
input=sys.stdin.readline

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

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

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

mod = 10**9+7

x=a[0]

for i in a[1:]:
    x=lcm(x,i)
ans=0
for i in range(n):
    ans+= x//a[i]

print(ans%mod)

Submission status: Accepted

Solution code:
from sys import stdin

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

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

readline = stdin.readline
num = int(readline())
d = list(map(int, readline().split()))
k = 1
MOD = 1000000007
ans = 0
for a in d:
    k = lcm(k, a)
for a in d:
    ans += k // a
print(ans % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def soinsu(n):
	l=defaultdict(int)
	for j in range(2,int(n**0.5)+1):
		while n%j==0:
			l[j]+=1
			n//=j
	if l=={}:
			l[n]+=1
	else:
		if n!=1:
			l[n]+=1
	for k,v in l.items():
		L[k]=max(L[k],v)

for i in range(n):
	soinsu(A[i])

LM=1
for k,v in L.items():
	LM*=k**v
	LM%=MOD

r=0
for i in range(n):
	r+=LM*pow(A[i],MOD-2,MOD)
	r%=MOD
print(r)