Problem:


Score : 700 points

Problem Statement

We have an integer sequence of length N: A_0,A_1,\cdots,A_{N-1}.

Find the following sum (\mathrm{lcm}(a, b) denotes the least common multiple of a and b):

\sum_{i=0}^{N-2} \sum_{j=i+1}^{N-1} \mathrm{lcm}(A_i,A_j)

Since the answer may be enormous, compute it modulo 998244353.

Constraints

1 \leq N \leq 200000

1 \leq A_i \leq 1000000

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_0\ A_1\ \cdots\ A_{N-1}

Output

Print the sum modulo 998244353.

Sample Input 1

3
2 4 6

Sample Output 1

22

\mathrm{lcm}(2,4)+\mathrm{lcm}(2,6)+\mathrm{lcm}(4,6)=4+6+12=22.

Sample Input 2

8
1 2 3 4 6 8 12 12

Sample Output 2

313

Sample Input 3

10
356822 296174 484500 710640 518322 888250 259161 609120 592348 713644

Sample Output 3

353891724



Sample input:
3
2 4 6


Sample output:
22

Submission status: Runtime Error

Solution code:
import math
N = int(input())
A = list(map(int , input().split()))
#result = 0;
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

def sigma2(func, frm, to):
    result1 = 0; #答えの受け皿
    for i in range(frm, to+1):
        result1 += func(A[frm - 1],A[i])
        #ここで関数を呼び出す。ちなみにここではi = x
    return result1
def sigma(sigma2, frm, to):
    result = 0; #答えの受け皿
    for i in range(frm, to+1):
        result += sigma2(lcm,i + 1,N - 1)
        #ここで関数を呼び出す。ちなみにここではi = x
    return result

if __name__ == "__main__":
    print(sigma(sigma2,0,N - 2) % 998244353)

Submission status: Runtime Error

Solution code:
import math

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


N = int(input())
A = input().split()
S = 0
for i in range(len(A)):
    A[i] = int(A[i])

for i in range(N-1):
    for j in range(i+1,N):
        S += lcm(A[i],A[j])
        S = S % 998244353

print(S)

Submission status: Runtime Error

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


N = int(input())
A = input().split()
S = 0
for i in range(len(A)):
    A[i] = int(A[i])

for i in range(N-1):
    for j in range(i+1,N):
        S += lcm(A[i],A[j])
        S = S % 998244353

print(S)

Submission status: Runtime Error

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

N = int(input())
A = input().split()
S = 0
for i in range(len(A)):
    A[i] = int(A[i])

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

print(S % 998244353)

Submission status: Runtime Error

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

import sys

#inFile = ''
inFile = 'test2.txt'
if inFile != '':
    f = open(inFile, 'r')
    sys.stdin = f
input = sys.stdin.readline

def lineInput(tList):#ex. tList = 'sdf'
    buf = list(input().strip().split())
    ret = []
    for i in range(len(tList)):
        if tList[i]=='d':
            ret.append(int(buf[i]))
        elif tList[i]=='f':
            ret.append(float(buf[i]))
        else:
            ret.append(buf[i])
    return ret

def gridInput(N):
    grid = []
    t = 'd'*N
    for i in range(N):
        array  = lineInput(t)
        grid.append(array)
    return grid

def outputList(l):
    for i,d in enumerate(l):
        if i < len(l)-1:
            print(d, end=" ")
        else:
            print(d)    

def outputGrid(grid):
    for x in grid:
        outputList(x)
            
#[n] = lineInput("d")
#g = gridInput(n)
#outputGrid(g)

def modlog(x, y):
    r = x % y
    return r

def gcd(x, y):
    r = modlog(x, y)
    while r != 0:
        x = y
        y = r
        r = modlog(x, y)
    return y

def kobai(x,y):
    z = gcd(x,y)
    return x*y/z

def mondai(N, List):
    ret=0
    for i in range(0,N-1):
        for j in range(i+1,N):
            x = kobai(List[i],List[j])
            ret += x
            ret %= 998244353
    return int(ret)

[N] = lineInput("d")
s = "d"*N
List = lineInput(s)

ans = mondai(N, List)

print(ans)

Submission status: Runtime Error

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

import sys

#inFile = ''
inFile = 'test1.txt'
if inFile != '':
    f = open(inFile, 'r')
    sys.stdin = f
input = sys.stdin.readline

def lineInput(tList):#ex. tList = 'sdf'
    buf = list(input().strip().split())
    ret = []
    for i in range(len(tList)):
        if tList[i]=='d':
            ret.append(int(buf[i]))
        elif tList[i]=='f':
            ret.append(float(buf[i]))
        else:
            ret.append(buf[i])
    return ret

def gridInput(N):
    grid = []
    t = 'd'*N
    for i in range(N):
        array  = lineInput(t)
        grid.append(array)
    return grid

def outputList(l):
    for i,d in enumerate(l):
        if i < len(l)-1:
            print(d, end=" ")
        else:
            print(d)    

def outputGrid(grid):
    for x in grid:
        outputList(x)
            
#[n] = lineInput("d")
#g = gridInput(n)
#outputGrid(g)

def modlog(x, y):
    r = x % y
    return r

def gcd(x, y):
    r = modlog(x, y)
    while r != 0:
        x = y
        y = r
        r = modlog(x, y)
    return y

def kobai(x,y):
    z = gcd(x,y)
    return x*y/z

def mondai(N, List):
    ret=0
    for i in range(0,N-1):
        for j in range(i+1,N):
            x = kobai(List[i],List[j])
            ret += x
            if ret >= 998244353:
                ret -= 998244353
    return int(ret)

[N] = lineInput("d")
s = "d"*N
List = lineInput(s)

ans = mondai(N, List)

print(ans)

Submission status: Runtime Error

Solution code:
mod = 998244353

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

n = int(input())
arr = list(map(int,input().split()))
sum=0
for i in range(len(arr)):
    for j in range(i+1,len(arr)):
        sum += lcm(arr[i],arr[j])
print(sum%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
A=[int(x) for x in input().split()]
import itertools
import math
com = list(itertools.combinations(A, 2))
res = 0
waru=998244353
for a, b in com:
    res += a*b // math.gcd(a,b) % waru

print(res % waru)

Submission status: Runtime Error

Solution code:
import numpy as np
import math

N=int(input())

A=np.array(input().split(),dtype=np.int64)

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


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

print(s%998244353)