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: Time Limit Exceeded

Solution code:
import sys
import math

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

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

pos=input()
N=int(pos)
A=input()
A=A.split()
sum=0
A=[int(item) for item in A]
for i in range(0,N-1):
    for j in range(i+1,N):
        sum=sum+int(lcm(A[i],A[j]))
print(int(sum%998244353))

Submission status: Time Limit Exceeded

Solution code:
def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x % y!=0:
            z = x % y
            x = y
            y = z
        else:
            return z

    

def least(x, y):
    ans = int((x * y) / gcd(x, y))
    return ans


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

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

print(S)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
 
def lcm(a,b):
  return a*b//gcd(a,b)

mod = 998244353
def add(a,b):return((a+b)%mod)
def sub(a,b):return((a+mod-b)%mod)
def mul(a,b):return(((a%mod)*(b%mod))%mod)
def power(x,y):return(pow(x,y,mod))
def div(a,b):return(mul(a,pow(b,mod-2,mod)))

N=int(input())
A=list(map(int,input().split()))
s=0
for i in range(N-1):
  for j in range(i+1,N):
    s=add(s,lcm(A[i],A[j]))
#    print(i,j,N,A,s)
print(s)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
A = list(map(int, input().split()))
sum = 0
pair = dict()


def lcm(a, b):
    global pair
    p = tuple(sorted([a, b]))
    from_cache = pair.get(p)
    if from_cache:
        return from_cache
    else:
        rst = a*b//fractions.gcd(a, b)
        pair[p] = rst
        return rst


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

sum = sum%998244353
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        lcm = a[i] // fractions.gcd(a[i], a[j]) * a[j]
        ans += lcm

print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
  
  
N = int(input())
L = list(map(int, input().split()))

#lcm_sum = 0
#for i in (list(itertools.combinations(L,2))):
#  lcm_sum += lcm(i[0], i[1])
kumi_list = list(itertools.combinations(L,2))
new_list = [lcm(i[0], i[1]) for i in kumi_list]

print(sum(new_list) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
A = list(map(int, input().split()))
sum = 0
pair = dict()


def lcm(a, b):
    global pair
    p = tuple(sorted([a, b]))
    from_cache = pair.get(p)
    if from_cache:
        return from_cache
    else:
        rst = a*b//fractions.gcd(a, b)
        pair[p] = rst
        return rst


for i in range(n-1):
    for j in range(i+1, n):
        sum += lcm(min(A[i], A[j]), max(A[i], A[j]))

sum = sum%998244353
print(sum)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import fractions
N = int(input())
P_list = list(map(int, input().split()))

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        ans += lcm(P_list[i], P_list[j])
        if ans >= 998244353:
            ans = ans % 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

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

lcm = 0
for i in range(0,N-1):
    for j in range(i+1,N):
        a = int(n[i])
        b = int(n[j])
       
        lcm += (a * b) // fractions.gcd(a, b)

print(lcm % 998244353)

Submission status: Time Limit Exceeded

Solution code:
#LCM GCD
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a
 
def lcm(a,b):
  return a*b//gcd(a,b)

mod = 998244353
def add(a,b):return((a+b)%mod)
def sub(a,b):return((a+mod-b)%mod)
def mul(a,b):return(((a%mod)*(b%mod))%mod)
def power(x,y):return(pow(x,y,mod))
def div(a,b):return(mul(a,pow(b,mod-2,mod)))

N=int(input())
A=list(map(int,input().split()))
s=0
for i in range(N-1):
  for j in range(i+1,N):
    s=add(s,lcm(A[i],A[j]))
#    print(i,j,N,A,s)
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd

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

input = sys.stdin.readline

N = int(input())
A = [int(a) for a in input().split()]

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

print(res)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
A = list(map(int, input().split()))
sum = 0
pair = dict()


def lcm(a, b):
    global pair
    pair_str = "{},{}".format(a, b)
    from_cache = pair.get(pair_str)
    if from_cache:
        return from_cache
    else:
        rst = a*b//fractions.gcd(a, b)
        pair[pair_str] = rst
        return rst


for i in range(n-1):
    for j in range(i+1, n):
        sum += lcm(min(A[i], A[j]), max(A[i], A[j]))

sum = sum%998244353
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
A = list(map(int, input().split()))
sum = 0
pair = dict()


def lcm(a, b):
    global pair
    pair_str = "{},{}".format(a, b)
    from_cache = pair.get(pair_str)
    if from_cache:
        return from_cache
    else:
        rst = a*b//fractions.gcd(a, b)
        pair[pair_str] = rst
        return rst


for i in range(n-1):
    for j in range(1, n):
        if i >= j:
            continue
        sum += lcm(min(A[i], A[j]), max(A[i], A[j]))

sum = sum%998244353
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

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

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N-1):
    for j in range(i+1, N):
        f=fractions.gcd(A[i],A[j])
        f2=A[i]*A[j]//f
        ans += f2
        ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import fractions
num = int(input())
numList = [int(i) for i in input().split()]
sum = 0
for idx in range(num -1):
    for idy in range(num)[idx + 1:]:
        sum += int(numList[idx] * numList[idy] /fractions.gcd(numList[idx], numList[idy]))
print(sum % 998244353)

Submission status: Time Limit Exceeded

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

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

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


d = [[0] * N for _ in range(N)]
answer = 0
for i in range(N-1):
    for j in range(i+1, N):
        if d[i][j] != 0:
            answer += d[i][j]
        else:
            d[i][j] = lcm(A[i], A[j])
            answer += d[i][j]
        answer %= 998244353

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
A = list(map(int, input().split()))
sum = 0


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


for i in range(n-1):
    for j in range(1, n):
        if i >= j:
            continue
        sum += lcm(A[i], A[j])

sum = sum%998244353
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

lst = [
  lcm(a[i], a[j])%998244353 for i in range(n) for j in range(i + 1, n)
]
print(sum(lst)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(x) for x in input().split()]
import itertools
#import fractions
from functools import lru_cache
com = list(itertools.combinations(A, 2))
res = 0
waru=998244353

@lru_cache(maxsize=None)
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a % b)


@lru_cache(maxsize=None)
def lcm(x,y):
    r = (x * y) // gcd(x, y) % waru
    return r

for a, b in com:
    res += lcm(a,b)

print(res % waru)

Submission status: Time Limit Exceeded

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

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

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

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

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = 0

import fractions

for i in range(n):
    for j in range(n):
        s += a[i] * a[j] // fractions.gcd(a[i], a[j])

s -= sum(a)
ans = s // 2

print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
  
  
N = int(input())
L = list(map(int, input().split()))

#lcm_sum = 0
#for i in (list(itertools.combinations(L,2))):
#  lcm_sum += lcm(i[0], i[1])
new_list = [lcm(i[0], i[1]) for i in list(itertools.combinations(L,2))]

print(sum(new_list) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

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

print(ret)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
sum = 0
def gcd(a,b):
    if b==0:
        return a
    return gcd(b, a%b)

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

for i in range(n-1):
    for j in range(i+1,n):
        sum += lcm(a[i],a[j])
print(sum%998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
  
  
N = int(input())
L = list(map(int, input().split()))

lcm_sum = 0

for i in (list(itertools.combinations(L,2))):
  lcm_sum += lcm(i[0], i[1])



print(lcm_sum % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import fractions
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 998244353

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

n = INT()
a = MAP()
ans=0

for i in range(n-1):
    for j in range(i+1,n):
        ans+=lcm(a[i],a[j])
    ans%=MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from fractions import gcd

input = sys.stdin.readline


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


def main():
    hoge = 998244353
    n = int(input())
    A = list(map(int, input().split()))
    print(sum([lcm(A[i], A[j]) for i in range(n - 1) for j in range(i + 1, n)]) % hoge)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from fractions import gcd

dic = {}

def lcm(a, b):
    r = dic.get((a, b))
    if r is None:
        r = a * b // gcd(a, b)
        dic[(a, b)] = r
    return r


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

ans = 0
for a, b in combinations(a, 2):
    ans += lcm(a, b)
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  n=int(input())
  N=list(map(int,input().split()))
  
  total=0
  for i in range(0,len(N)):
    for j in range(i+1,len(N)):
      c=N[i]
      d=N[j]
      while d!=0:
        c,d=d,c%d
      
      total+=N[i]*N[j]//c

  print(total%998244353)

if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
s = 0
for i in range(N):
  for j in range(i+1,N):
    s += lcm(A[i],A[j])
print(s%998244353)

Submission status: Time Limit Exceeded

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

from fractions import gcd

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

ans = 0

for i in range(n-1):
  for j in range(i+1, n):
    ans += lcm(a[i],a[j])
ans = ans % (998244353)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
A=[int(x) for x in input().split()]
import itertools
import fractions
from functools import lru_cache
com = list(itertools.combinations(A, 2))
res = 0
waru=998244353

@lru_cache(maxsize=None)
def lcm(x,y):
    r = (x * y) // fractions.gcd(x, y) % waru
    return r

for a, b in com:
    res += lcm(a,b)

print(res % waru)

Submission status: Time Limit Exceeded

Solution code:
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

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

sum_lcm = sum([lcm(a[i], a[j]) for i in range(N-1) for j in range(i+1, N)])
    
print(sum_lcm % 998244353)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import fractions

n = int(input())
a = list(map(int, input().split()))
aSum = 0
for i in range(0, n-1):
    for j in range(i + 1, n):
        aSum += a[i] * a[j] // fractions.gcd(a[i], a[j])
        aSum %= 998244353
print(aSum)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)

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

ans = 0
for a, b in combinations(a, 2):
    ans += lcm(a, b)
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

total=0
for i in range(0,len(N)):
  for j in range(i+1,len(N)):
    total+=lcm(N[i],N[j])

print(total%998244353)

Submission status: Time Limit Exceeded

Solution code:
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

N = int(input())
a = list(map(int, input().split()))
sum = 0

for i in range(N-1):
  for j in range(i+1, N):
    sum += (lcm(a[i], a[j]))
    
print(sum % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

def lcm(x, y):
    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: Time Limit Exceeded

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

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

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

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

print (ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N=int(input())

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

def gcd(m, n):
    while n:
        m, n = n, m % n
    return m

def lcm(x, y):
    return (x * y)//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)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
a = list(map(int, input().split()))
sum = 0

for i in range(N-1):
  for j in range(i+1, N):
    x = a[i]
    y = a[j]
    
    while y:
      x, y = y, x % y
      
    sum += (a[i] * a[j] // x)
print(sum % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N=int(input())

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm(x, y):
    return (x * y)//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)

Submission status: Time Limit Exceeded

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
def lcm(x, y):
    return (x * y) // gcd(x, y)

N = int(input())
a = list(map(int, input().split()))
sum = 0

for i in range(N-1):
  for j in range(i+1, N):
    sum += lcm(a[i], a[j])
print(sum % 998244353)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Accepted

Solution code:
mod=998244353
N=int(input())
A=[int(i) for i in input().split()]
M=10**6
B=[0 for i in range(M+1)]
for i in range(N):
    B[A[i]]+=1
C=[0 for i in range(M+1)]
for d in range(1,M+1):
    for dk in range(d,M+1,d):
        C[d]+=B[dk]*dk
isPrime=[1 for i in range(M+1)]
isPrime[0]=0;isPrime[1]=0
for i in range(M+1):
    if isPrime[i]==0:
        continue
    for j in range(2*i,M+1,i):
        isPrime[j]=0
Mebius=[1 for i in range(M+1)]
Mebius[0]=0
for i in range(2,M+1):
    if isPrime[i]==0:
        continue
    for j in range(i,M+1,i):
        Mebius[j]*=-1
for i in range(2,M+1):
    for j in range(i*i,M+1,i*i):
        Mebius[j]=0

f=[0 for i in range(M+1)]
for d in range(1,M+1):
    for n in range(d,M+1,d):
        f[n]+=d*Mebius[d]
for n in range(1,M+1):
    f[n]=f[n]*pow(n,mod-2,mod)
ans=0
for d in range(1,M+1):
    ans+=f[d]*C[d]*C[d]
    ans%=mod
tmp=0
for i in range(N):
    tmp+=A[i]
submit=(ans-tmp)*pow(2,mod-2,mod)
print(submit%mod)

Submission status: Accepted

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

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

def main():
    mod=998244353
    N=I()
    A=LI()
    MA=max(A)
    x=[0]*(MA+1)
    
    #数列x[i]はi*(iの個数)
    for i in range(N):
        x[A[i]]+=A[i]
        
    #print(x)
    
    #上位集合のゼータ変換
    for k in range(1,MA+1):
        for s in range(k*2,MA+1,k):#sが2kからkずつ増える=>sはkの倍数(自分自身を数えないため，2kから)
            x[k]=(x[k]+x[s])%mod
    
    #print(x)
    #この段階でx[i]はiを約数に持つやつの和(個数も加味している)
    
    #積演算
    for i in range(MA+1):
        x[i]=(x[i]*x[i])%mod
        
    #print(x)
    
    
    #メビウス変換で戻す
    for k in range(MA,0,-1):
        for s in range(k*2,MA+1,k):
            x[k]=(x[k]-x[s])%mod
            
    #この段階でx[i]はiをgcdに持つもの同士をかけたものの和
    #print(x)
    
    #gcdでわる
    ans=0
    for i in range(1,MA+1):
        if x[i]!=0:
            x[i]=(x[i]*pow(i,mod-2,mod))%mod
            ans=(ans+x[i])%mod
        
    #この段階でx[i]はiをgcdに持つもの同士のlcaの和
    #print(x)
        
    ans=(ans-sum(A))%mod
    #A[i],A[i]の組を除去する．A[i]動詞のくみはlcaがA[i]になる
       
    """ 
    ans=(ans*pow(2,mod-2,mod))%mod#A[i]*A[j] と　A[j]*A[i]の被り除去
    print(pow(2,mod-2,mod))=499122177
    """
    ans=(ans*499122177)%mod
    
    print(ans)
        
    
    

main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int((n+1)**0.5)+1):
        if is_prime[i]:
            for j in range(i *2, n + 1, i):
                is_prime[j] = False
    res = [i for i in range(n+1) if is_prime[i]]
    return res

def make_modinv_list(n, mod=10**9+7):
    inv_list = [0]*(n+1)
    inv_list[1] = 1
    for i in range(2, n+1):
        inv_list[i] = (mod - mod//i * inv_list[mod%i] % mod)
    return inv_list

def solve():
  mod = 998244353
  n = ni()
  a = nl()
  m = max(a)
  s = -sum(a) % mod
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  a = make_modinv_list(m, mod)
  pr = primes(m) 
  for i in pr:
    for j in range(m//i, 0, -1):
      l[j] += l[j*i]
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in pr:
    for j in range(1, m//i + 1):
      l[j] = (l[j] - l[j*i]) % mod
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * a[i]) % mod
  print(s * a[2] % mod)
  return

solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def modinv(x, mod):
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def solve():
  n = ni()
  a = nl()
  m = max(a)
  mod = 998244353
  l = [0]*(m+1)
  for x in a:
    l[x] += x
  sieve = [1]*(m+1)
  sieve[0] = sieve[1] = 0
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(m//i, 0, -1):
        sieve[j*i] = 0
        l[j] += l[j*i]
      sieve[i] = 1
  for i in range(m+1):
    l[i] = l[i] * l[i] % mod
  for i in range(2, m+1):
    if sieve[i]:
      for j in range(1, m//i + 1):
        l[j] -= l[j*i]
  s = -sum(a)
  for i in range(1, m+1):
    if l[i]:
      s = (s + l[i] * modinv(i, mod)) % mod
  print(s * modinv(2, mod) % mod)
  return

solve()

Submission status: Accepted

Solution code:
import sys


def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    solo_invs = [0] + [f * i % MOD for f, i in zip(factorials, invs[1:])]

    return factorials, invs, solo_invs


def decompose_inverses(solo_invs, MOD):
    # 各整数 g に対して、g の約数である各 i について dcm[i] を全て足すと 1/g になるような数列を作成
    n = len(solo_invs)
    dcm = solo_invs[:]
    for i in range(1, n):
        d = dcm[i]
        for j in range(2 * i, n, i):
            dcm[j] -= d
    for i in range(1, n):
        dcm[i] %= MOD
    return dcm


n, *aaa = map(int, sys.stdin.buffer.read().split())
MOD = 998244353
LIMIT = max(aaa)
count = [0] * (LIMIT + 1)
double = [0] * (LIMIT + 1)
for a in aaa:
    count[a] += a
    double[a] += a * a
_, _, solo_invs = prepare(LIMIT, MOD)
dcm = decompose_inverses(solo_invs, MOD)

ans = 0
inv2 = solo_invs[2]
for d in range(1, LIMIT + 1):
    ans = (ans + dcm[d] * (sum(count[d::d]) ** 2 - sum(double[d::d])) * inv2) % MOD
print(ans)

Submission status: Accepted

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


n = int(input())
a = list(map(int, input().split()))
MOD = 998244353
max_a = max(a)

c = [0] * (max_a + 1)
for i in range(1, max_a + 1):
    c[i] = pow(i, MOD - 2, MOD)

for i in range(1, max_a):
    j = i
    while True:
        j += i
        if j <= max_a:
            c[j] -= c[i]
            c[j] %= MOD
        else:
            break

cnt = [0] * (max_a + 1)
for i in range(n):
   cnt[a[i]] += 1

ans = 0
for i in range(1, max_a + 1):
    tmp0 = 0
    tmp1 = 0
    j = i
    while True:
        if j <= max_a:
            tmp0 += cnt[j] * j
            tmp1 += cnt[j] * (j ** 2)
        else:
            break
        j += i
    tmp0 *= tmp0
    ans += (tmp0 - tmp1) * c[i]
    ans %= MOD

print((ans * pow(2, MOD - 2, MOD)) % MOD)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MOD = 998244353

max_a = max(a)
c = [0] * (max_a + 1)
for i in range(1, max_a + 1):
    c[i] = pow(i, MOD - 2, MOD)

for i in range(1, max_a):
    j = i
    while True:
        j += i
        if j <= max_a:
            c[j] -= c[i]
            c[j] %= MOD
        else:
            break

cnt = [0] * (max_a + 1)
for i in range(n):
   cnt[a[i]] += 1

ans = 0
for i in range(1, max_a + 1):
    tmp0 = 0
    tmp1 = 0
    j = i
    while True:
        if j <= max_a:
            tmp0 += cnt[j] * j
            tmp1 += cnt[j] * (j ** 2)
        else:
            break
        j += i
    tmp0 *= tmp0
    ans += (tmp0 - tmp1) * c[i]
    ans %= MOD

print((ans * pow(2, MOD - 2, MOD)) % MOD)

Submission status: Accepted

Solution code:
mod = 998244353
n = int(input())
a = list(map(int, input().split()))
m = max(a)
cnt = [0]*(m+1)
for ai in a:
    cnt[ai]+=1
ans = 0
res = [0]*(m+1)
for i in range(1, m+1)[::-1]:
    sm = 0
    sq = 0
    for j in range(i, m+1, i):
        sm+=j*cnt[j] 
        sq+=cnt[j]*j*j
        res[i]-=res[j]
    res[i]+=sm*sm-sq
    ans+=res[i]//i
    ans%=mod
print(ans*(pow(2, mod-2, mod))%mod)

Submission status: Accepted

Solution code:
MOD = 998244353

def zeta_gcd(a,primes):
    n = len(a)-1
    for p in primes:
        for i in range(n//p,0,-1):
            a[i] += a[p*i]
            a[i] %= MOD
def mobius_gcd(a,primes):
    n = len(a)
    for p in primes:
        for i in range(1,n):
            if i*p >= n: break
            a[i] -= a[p*i] 
            a[i] %= MOD
def get_primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

NNN = 10**6 + 1
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )

N, = map(int, input().split())
X = list(map(int, input().split()))
primes = get_primes(NNN)
fs = [0]*NNN
for x in X:
    fs[x] += x
#print(fs)
zeta_gcd(fs, primes)
#print(fs)
for i, x in enumerate(fs):
    fs[i] = x**2
#print(fs)
mobius_gcd(fs, primes)
#print(fs)
r = 0
for i, f in enumerate(fs[1:]):
    i += 1
    r = (r + f*inverse[i]) % MOD
for x in X:
    r = (r - x) % MOD

print((r*inverse[2])%MOD)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
V=max(A)
mod=998244353
data=[0]*(V+1)
data[1]=1
for i in range(2,V+1):
    data[i]=-(mod//i)*data[mod%i]%mod
for i in range(1,V+1):
    for j in range(2,V//i+1):
        data[i*j]=(data[i*j]-data[i])%mod
lst=[0]*(V+1)
for a in A:
    lst[a]+=1
mod_2=pow(2,mod-2,mod)
ans=0
for i in range(1,V+1):
    sum_1=0
    sum_2=0
    for j in range(1,V//i+1):
        zzz=i*j
        sum_1+=zzz*lst[zzz]
        sum_2+=zzz**2*lst[zzz]
    ans=(ans+(sum_1**2-sum_2)*data[i]*mod_2)%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline    
MOD = 998244353
N = int(readline())
A = list(map(int, readline().split()))
mA = max(A) + 1
T = [0]*mA
i2 = pow(2, MOD-2, MOD)


table = [0]*mA
table2 = [0]*mA
for a in A:
    table[a] = (table[a] + a)%MOD
    table2[a] = (table2[a] + a*a)%MOD
prime = [True]*mA
for p in range(2, mA):
    if not prime[p]:
        continue
    for k in range((mA-1)//p, 0, -1):
        table[k] = (table[k] + table[k*p])%MOD
        table2[k] = (table2[k] + table2[k*p])%MOD
        prime[k*p] = False

T = [(x1*x1-x2)*i2%MOD for x1, x2 in zip(table, table2)]

ans = 0
coeff = [0]*mA
for i in range(1, mA):
    k = T[i]
    l = - coeff[i] + pow(i, MOD-2, MOD)
    ans = (ans+l*k)%MOD
    for j in range(2*i, mA, i):
        coeff[j] = (coeff[j] + l)%MOD
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=998244353
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        self.__fact[n]*self.__invfact[k]%MOD

def prime(n):
    if n<=1: return []
    S=[1]*(n+1)
    S[0]=0; S[1]=0
    for i in range(2,n):
        if(S[i]==0): continue
        for j in range(2*i,n+1,i): S[j]=0
    return [p for p in range(n+1) if(S[p])]

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    V=max(A)
    C=[0]*(V+1)
    for a in A: C[a]+=1

    P=prime(V)
    W=[1]*(V+1)
    for p in P:
        for i in range(p,V+1,p):
            W[i]*=(1-p)
    mf=modfact(V)
    for i in range(1,V+1):
        W[i]=(W[i]*mf.inv(i))%MOD

    ans=0
    for d in range(1,V+1):
        s=0 # 和(後に2乗する)
        t=0 # 2乗の和
        for i in range(d,V+1,d):
            s+=i*C[i]%MOD
            t+=(i**2)*C[i]%MOD
        ans+=(W[d]*(s**2-t))%MOD*mf.inv(2)%MOD
    print(ans%MOD)
resolve()