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: Wrong Answer

Solution code:
import sys 
from functools import reduce
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
lcm = reduce(lambda x,y:x*y//gcd(x,y),A)
lcm %= mod
ans = 0
for i in range(N):
    ans += lcm//A[i]%mod
print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys 
from math import gcd
import numpy as np
from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
@jit(cache=True)
def lcm(N,a):
    x = a[0]
    for i in range(1, N):
        x = (x * a[i]) // gcd(x, a[i])
    ans = 0 
    for i in range(N):
        ans += x // a[i] % mod
    return ans%mod
A = np.array(A,np.int64)
ans = lcm(N,A)
print(ans)

Submission status: Wrong Answer

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl={}
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl.get(i,"a")=="a" or kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl.get(n,"a")=="a" or kl[n]<cnt:
                kl[n]=1
                
    lcm=1
    for a,b in kl.items():
        lcm*=a**b
        lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
#

import sys
input=sys.stdin.readline

MOD=10**9+7
            
def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    kl={}
    for j in range(N):
        n=A[j]
        for i in range(2,int((n)**0.5)+1):
            if n%i==0:
                cnt=0
                while(n%i==0):
                    n/=i
                    cnt+=1
                if kl.get(i,"a")=="a" or kl[i]<cnt:
                    kl[i]=cnt
        if n!=1:
            if kl.get(n,"a")=="a" or kl[n]<cnt:
                kl[n]=1
                
    lcm=1
    print(kl)
    for a,b in kl.items():
        lcm*=a**b
        lcm%=MOD
    ans=0
    for i in range(N):
        ans+=lcm*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

Solution code:
#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    
    for i in range(2,N):
        l=(l*A[i])%(10**9+7)
        l//=gcd(A[i],l-A[i])
    ans=0
    for i in range(N):
        bi=l//A[i]
        ans+=bi
        ans%=10**9+7
    print(ans)
    
    
    
if __name__=="__main__":
    main()

Submission status: Wrong Answer

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

g = fractions.gcd(a[0],a[1])
l = a[0]*a[1]//g
mod = 10**9+7

if n == 2:
    print(l//a[0] + l//a[1])
    exit()
else:
    for i in range(n-2):
        g = l*a[i+2]//fractions.gcd(l,a[i+2])

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

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import defaultdict
from functools import reduce
import collections 
stdin = sys.stdin
         
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))
     
INF=10**18
mod=10**9+7
N=int(input())
A=nl()
NMAX=10**6
class Sieve:
    def __init__(self,n):
        self.n=n
        self.f=[0]*(n+1)
        self.prime=[]
        self.f[0]=self.f[1]=-1
        for i in range(2,n+1):
            if(self.f[i]):
                continue
            else:
                self.prime.append(i)
                self.f[i]=i
                for j in range(i*i,n+1,i):
                    if(~self.f[j]):
                        self.f[j]=i
    def isProme(self,x):
        return (self.f[x]==x)
    def factorList(self,x):
        res=[]
        while(x!=1):
            res.append(self.f[x])
            x//=self.f[x]
        return res
    def factor(self,x):
        fl=self.factorList(x)
        return collections.Counter(fl)
        


                
                
            
        
        
def get_sieve_of_eratosthenes(n):
    prime = [2]
    limit = int(n**0.5)
    data = [i + 1 for i in range(2, n, 2)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]



sieve=Sieve(10**6)
mp=defaultdict(int)
for i in range(N):
    f=sieve.factor(A[i])
    for key,val in f.items():
        mp[key]=max(val,mp[key])


lcm=1
for key,val in mp.items():
    lcm*=(key**val)


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

print(ans)

Submission status: Wrong Answer

Solution code:
# from fractions import gcd
# P = 10**9+7
# N = int(input())
# S = list(map(int, input().split()))

# l = {2:0}
# for num in S:
#     temp = num
#     M = temp//2+2
#     cnt = 0
#     while temp%2 == 0:
#         cnt += 1
#         temp //= 2
#     l[2] = max(l[2], cnt)
#     i = 3
#     while temp > 1 and i < M:
#         cnt = 0
#         while temp%i == 0:
#             cnt += 1
#             temp //= i
#         if cnt > 0:
#             if i in l:
#                 l[i] = max(l[i], cnt)
#             else:
#                 l[i] = cnt
#         i += 2
#     if temp > 1:
#         if temp in l:
#             l[temp] = max(l[temp], 1)
#         else:
#             l[temp] = 1
    
    
# ans = 0
# for i in range(N):
#     ans = (temp//S[i]+ans)%P
# print(ans)



from fractions import gcd
P = 10**9+7
N = int(input())
S = list(map(int, input().split()))
 
temp = S[0]
for i in range(1, N):
    temp = temp*S[i] // gcd(temp, S[i])
    temp %= P
 
ans = 0
for num in S:
    ans = ((temp*pow(num, P-2, P))%P+ans)%P
print(ans)

Submission status: Wrong Answer

Solution code:
mod = 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, modInverse(x, mod)))
    
    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: Wrong Answer

Solution code:
mod = 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] = 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, modInverse(x, mod)))
    
    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: Wrong Answer

Solution code:
mod = 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):
    print(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 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] = 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
    
    for x in arr:
        #print(my_inv(x))
        ans = add(ans, lcm / 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: Wrong Answer

Solution code:
import numpy as np
from functools import reduce

def gcd1(m, n):
    r = m % n
    return gcd1(n, r) if r else n
def lcm1(m, n):
    return m//gcd1(m, n)*n
def lcm(numbers):
    return reduce(lcm1, numbers, 1)

MOD = 10**9+7
n = int(input())
a = np.array(list(map(int, input().split())))
l = lcm(a)
ans = 0
for x in a:
    ans = (ans + l//x)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def lcm(m, n):
    return m//gcd(m, n)*n
MOD = 10**9+7
n = int(input())
a = np.array(list(map(int, input().split())))
l = a[0]
for i in range(1,n):
    l = lcm(a[i], l)
ans = 0
for x in a:
    ans = (ans + l//x)%MOD
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    def prime_pair(n):
        pairs = {}
        tmp = n
        for i in range(2, n):
            if i * i > n:
                break
            if tmp % i != 0:
                continue
            ex = 0
            while tmp % i == 0:
                ex += 1
                tmp /= i
            pairs[i] = ex
        if tmp != 1:
            pairs[int(tmp)] = 1
        return pairs

    N = int(input())
    a_list = list(map(int, input().split()))
    a_pp_list = []
    MOD = 10**9 + 7

    a_lcm = {}
    key_set = set()
    for a in a_list:
        a_pp = prime_pair(a)
        a_pp_list.append(a_pp)
        for k in a_pp.keys():
            if k not in key_set:
                a_lcm[k] = a_pp[k]
            else:
                a_lcm[k] = max(a_lcm[k], a_pp[k])

    res = 0
    for a_pp in a_pp_list:
        b = 1
        for k in a_lcm.keys():
            if k in a_pp.keys():
                b *= (k**(a_lcm[k] - a_pp[k])) 
            else:
                b *= k**a_lcm[k]
            b %= MOD
        res += b
    print(res)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections
import numpy as np

MOD = 1000000007  # type: int

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[i] = cnt

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

    if arr==[]:
        arr[n] = 1

    return arr


def solve(N: int, A: "List[int]"):
    LCM = collections.defaultdict(int)

    for a in A:
        primes = factorization(a)
        for k, v in primes.items():
            LCM[k] = max(LCM[k], v)

    LCM_val = np.prod([pow(k, v) for k, v in LCM.items()])
    result = sum([(LCM_val // a) for a in A])
    print(result % MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections

MOD = 1000000007  # type: int

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[i] = cnt

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

    if arr==[]:
        arr[n] = 1

    return arr


def solve(N: int, A: "List[int]"):
    LCM = collections.defaultdict(int)

    for a in A:
        primes = factorization(a)
        for k, v in primes.items():
            LCM[k] = max(LCM[k], v)

    result = 0
    for a in A:
        primes = factorization(a)
        tmp = 1
        for k, v in LCM.items():
            tmp *= pow(k, v-primes[k] if k in primes else v, MOD)
        result += tmp
    print(result % MOD)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

Submission status: Wrong Answer

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

MOD = 10**9+7

from collections import Counter

def prime(n):
    p = Counter()

    while not n % 2:
        p[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            p[i] += 1
            n //= i
        i += 2
        
    if n > 1: p[n] += 1
    
    return p

c = Counter()
for a in A:
    p = prime(a)

    for key, value in p.items():
        c[key] = max(c[key], value)

n = 1
for key, value in c.items():
    n *= key**value

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

print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
A=[int(a) for a in 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

q=lcm(A)
ans=0
for i in range(N):
    ans+=q//A[i]
print(ans%(10**9+7))
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
factmemo = [{} for _ in range((10**6+1))]
def fact(n):
    dict = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if factmemo[temp]!={}:
            # 合併してreturn
            dtmp = dict
            dict = factmemo[temp]
            for k,v in dtmp.items():
                if k in dict:
                    dict[k] += v
                else:
                    dict[k] = v
            factmemo[n] = dict
            return dict

        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

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

    if dict=={}:
        dict[n] = 1

    factmemo[n] = dict
    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7
factmemo = [{} for _ in range((10**6+1))]
def fact(n):
    dict = {}
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if factmemo[temp]!={}:
            # 合併してreturn
            dtmp = dict
            dict = factmemo[temp]
            for k,v in dtmp.items():
                if k in factmemo[temp]:
                    dict[k] += v
                else:
                    dict[k] = v
            factmemo[n] = dict
            return dict

        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            dict[i] = cnt

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

    if dict=={}:
        dict[n] = 1

    factmemo[n] = dict
    return dict

def lcm(arr):
    # 素因数分解をもとにarr全体のLCMを求める
    lcm = 1
    factor = {}
    for a in arr:
        f = fact(a)
        for k,v in f.items():
            if k in factor:
                tmp = factor[k]
                factor[k] = max(factor[k],v)
                lcm *= pow(k,max(0, v-tmp),MOD)
            else:
                factor[k] = v
                lcm *= pow(k,v,MOD)

    return lcm

def main():
    N = int(input())
    A = list(map(int, input().split()))
    # 方針.A全体のlcmをLとすると、ans=Σ(i=[0,N])x/Ai
    ans = 0
    L = lcm(A)
    for a in A:
        ans += (L//a)%MOD
        ans %= MOD
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
from fractions import gcd

mod = 10 ** 9 + 7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception("modular inverse does not exist")
    else:
        return x % m


n = int(input())
A = list(map(int, input().split()))
lcm = A[0]
for i in range(n):
    g = gcd(lcm, A[i])
    lcm = lcm * A[i] // g
    lcm %= mod
ans = 0
for i in range(n):
    gyaku = modinv(A[i], mod)
    ans += lcm * gyaku
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
from functools import reduce
from operator import mul

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)
    b = Counter(a)
    return b

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    fac = prime_factorize(A[0]) | prime_factorize(A[1])
    for x in A[2:]:
        fac |= prime_factorize(x)
    ans = 0
    f = [pow(x[0],x[1],100000007) for x in fac.items()]
    if len(f) > 0:
        lcm = reduce(mul,f)
    else:
        lcm = 1
    print(sum([(lcm//x) % 100000007 for x in A]))

Submission status: Wrong Answer

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print('1')
else:
    gcd = xgcd(A[0],A[1])[0]
    lcm = (A[0]*A[1]) // gcd
    for x in A[2:]:
        if max(lcm,x) % min(lcm,x) == 0:
            gcd = min(lcm,x)
        else:
            gcd = xgcd(lcm,x)[0]
        lcm = lcm * x * modinv(gcd,1000000007)
    ans = 0
    for x in A:
        ans = (ans + (lcm // x)) % 1000000007
    print(ans)

Submission status: Wrong Answer

Solution code:
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

N = int(input())
A = list(map(int, input().split()))
if N == 1:
    print(A[0])
else:
    gcd = xgcd(A[0],A[1])
    lcm = (A[0] * A[1]) // gcd
    for i in range(2,N):
        gcd = xgcd(lcm,A[i])
        lcm = (lcm * A[i]) // gcd
    print(sum([lcm // x for x in A])%1000000007)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 < n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)
            


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    A = LI()
    d = {}

    for x in A:
        for i in range(2,int(math.sqrt(x))+1):
            cnt = 0
            while x % i == 0:
                cnt += 1
                x //= i
            if i in d:
                d[i] = max(d[i],cnt)
            else:
                d[i] = cnt
            if x == 1: break
        else:
            if x in d:
                d[x] = max(d[x],1)
            else:
                d[x] = 1
    m = 1
    for i,x in d.items():
        m = (m * i ** x) % MOD
    ans = 0
    for x in A:
        ans += (m * pow(x,MOD-2,MOD)) % MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections as col

def prime(n):
    ans = []
    for i in range(2, int(n**0.5)+1):
        while not n%i: n //= i ; ans.append(i)
    if n != 1: ans.append(num)
    return col.Counter(ans)
    
n = int(input())
a = list(map(int,input().split()))

cnt = col.Counter()
for num in a:
    new = prime(num)
    for key,val in new.items():
        if val > cnt[key] : cnt[key] = val

LCM = 1
MOD = 10**9 + 7
for key,val in cnt.items(): LCM *= key**val %MOD

ans = 0
for num in a:
    b = LCM * pow(num, MOD-2, MOD) #割るのではなく逆元をかける
    ans += b
    
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
import fractions
import functools

def multiple(a, b):
    return a*b // fractions.gcd(a, b)
def lcm(nums):
  return functools.reduce(multiple, nums)

def main():
  N = int(input())
  A = list(map(int, input().split()))
  A = set(A)
  n = lcm(A)
  ans = 0
  mod = 10**9+7
  for a in A:
    ans += n//a
    ans %= mod

  print(ans)

if __name__ == "__main__":
  main()

Submission status: Wrong Answer

Solution code:
import fractions
import functools

def multiple(a, b):
    return a*b // fractions.gcd(a, b)
def lcm(nums):
  return functools.reduce(multiple, nums)

def main():
  N = int(input())
  A = list(map(int, input().split()))
  n = lcm(A)
  ans = 0
  mod = 10**9+7
  for a in A:
    ans += n//a
    ans %= mod
  print(n)
  print(ans)

if __name__ == "__main__":
  main()