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

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
from collections import Counter
c = Counter(a)
M = 10**9 + 7
V = max(a)
ans = 0
f = [0]*(V+1)
w2 = pow(2, M-2, M)
for g in range(V, 0, -1):
    val = 0
    val2 = 0
    val3 = 0
    for i in range(1, (V//g) + 1):
        val += (g*i)*c[i*g]
        val2 += ((g*i)**2)*c[i*g]
        val3 += f[(i)*g]
        val %= M
        val2 %= M
        val3 %= M
#     val3 = sum(f[i] for i in range(2*g, V+1, g))
#     print(g, V//g, val, val2, val3)
    f[g] = ((val**2 - val2)*w2 - val3) % M
    ans += f[g] * pow(g, M-2, M)
    ans %= M
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
MOD = 998244353
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)

pws = [1 for _ in range(1000001)]
for i in range(1, 1000001):
	pws[i] = (pws[i-1] * 2) % MOD

res = [0 for _ in range(1000001)]
ans = 0

for i in range(1000000, 0, -1):
	sum_of_sq, sq_of_sum = 0, 0
	for j in range(i, 1000001, i):
		sum_of_sq += pws[j] * c[j]
		sum_of_sq %= MOD
		sq_of_sum += j * c[j]
		sq_of_sum %= MOD
	sq_of_sum = pow(sq_of_sum, 2, MOD)
	res[i] = (sq_of_sum - sum_of_sq) * pow(2*i, MOD-2, MOD)
	res[i] %= MOD
	for j in range(2*i, 1000001, i):
		res[i] -= res[j] * (j//i)
		res[i] %= MOD
	ans += res[i]
	ans %= MOD

print(ans)

Submission status: Wrong Answer

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

Solution code:
a = int(input())
b = list(map(int,input().split()))
if len(b)!=1:
    b.sort()
    mx=max(b)
    l=[2]
    for i in range(2,mx):
        for n,j in enumerate(l):
            if i%j==0:
                break
            if n==len(l)-1:
                l.append(i)
    d=0
    lis=[]
    for i in b:
        t=i
        li=[]
        while t!=1:
            for j in l:
                if t%j==0:
                    t=t/j
                    li.append(j)
                    break
        lis.append(li)
    for j in range(len(lis)-1):
        for m in range(j+1,len(lis)):
            c=1
            for n,i in enumerate(l):
                if lis[j].count(i)<=lis[m].count(i) and lis[m].count!=0:
                    c=(c*(i**int(lis[m].count(i))))%998244353
                elif  lis[j].count(i)>lis[m].count(i):
                    c=(c*(i**int(lis[j].count(i))))%998244353
            d+=c
    print(d%998244353)
else :
    print(b[0])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
e = 998244353
import fractions
ans = 0
for i in range(N-1):
    x = A[i]
    for j in range(i+1,N):
        y = A[j]
        g = fractions.gcd(x,y)
        l = (x*y)//g
        ans += l % e
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
e = 998244353
import fractions
ans = 0
for i in range(N):
    x = A[i]
    for j in range(i+1,N):
        y = A[j]
        g = fractions.gcd(x,y)
        l = (x*y)//g
        ans += l % e
print(ans)

Submission status: Wrong Answer

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

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

numsum = 0
for i in range(n-1):
    for j in  range(i+1,n):
        a = p[i]
        b = p[j]
        numsum+= a * b / gcd(a, b)

print(int(numsum%998244353))

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction

input = sys.stdin.readline

N = int(input()) # integer
A = list(map(int,input().split())) # list
M = 998244353

amax = max(A)
w = [1]*amax
for i in range(1,amax+1):
	n = 2
	j = i*n
	while j<=amax:
		w[j-1] -= w[i-1]*n
		n += 1
		j += i

count = [0]*amax
for i in range(N):
	count[A[i]-1] += 1

ans = 0
for i in range(1,amax+1):
	isum = 0
	isumr = 0
	sqsum = 0
	j = i
	while j<=amax:
		isum += j*count[j-1]
		sqsum += j*j*count[j-1]
		j += i

	ans += round(((isum**2-sqsum)/2)*w[i-1]//i)
	ans = ans%M

print(ans%M)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction

input = sys.stdin.readline

N = int(input()) # integer
A = list(map(int,input().split())) # list
M = 998244353

amax = max(A)
w = [1]*amax
for i in range(1,amax+1):
	n = 2
	j = i*n
	while j<=amax:
		w[j-1] -= w[i-1]*n
		n += 1
		j += i

count = [0]*amax
for i in range(N):
	count[A[i]-1] += 1

ans = 0
for i in range(1,amax+1):
	isum = 0
	isumr = 0
	sqsum = 0
	j = i
	while j<=amax:
		isum += j*count[j-1]
		sqsum += j*j*count[j-1]
		j += i

	ans += ((isum**2-sqsum)/2)*w[i-1]//i
	ans = ans%M

print(ans%M)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction

input = sys.stdin.readline

N = int(input()) # integer
A = list(map(int,input().split())) # list
M = 998244353

amax = max(A)
w = [1]*amax
for i in range(1,amax+1):
	n = 2
	j = i*n
	while j<=amax:
		w[j-1] -= w[i-1]*n
		n += 1
		j += i

count = [0]*amax
for i in range(N):
	count[A[i]-1] += 1

ans = 0
for i in range(1,amax+1):
	isum = 0
	isumr = 0
	sqsum = 0
	j = i
	while j<=amax:
		isum += j*count[j-1]
		sqsum += j*j*count[j-1]
		j += i

	ans += int(((isum**2-sqsum)/2)*w[i-1]/i)
	ans = ans%M

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction

input = sys.stdin.readline

N = int(input()) # integer
A = list(map(int,input().split())) # list
M = 998244353

amax = max(A)
w = [1.0/i for i in range(1,amax+1)]

for i in range(1,amax+1):
	j = i*2
	while j<=amax:
		w[j-1] -= w[i-1]
		j += i

count = [0]*amax
for i in range(N):
	count[A[i]-1] += 1

ans = 0
for i in range(1,amax+1):
	isum = 0
	sqsum = 0
	j = i
	while j<=amax:
		isum += j*count[j-1]
		sqsum += j**2*count[j-1]
		j += i

	ans += int((round(isum*w[i-1])*isum-round(sqsum*w[i-1]))/2)
	# ans += round(((isum**2-sqsum)/2)*w[i-1])
	ans = ans%M

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from fractions import Fraction

input = sys.stdin.readline

N = int(input()) # integer
A = list(map(int,input().split())) # list
M = 998244353

amax = max(A)
w = [1.0/i for i in range(1,amax+1)]

for i in range(1,amax+1):
	j = i*2
	while j<=amax:
		w[j-1] -= w[i-1]
		j += i

count = [0]*amax
for i in range(N):
	count[A[i]-1] += 1

ans = 0
for i in range(1,amax+1):
	isum = 0
	sqsum = 0
	j = i
	while j<=amax:
		isum += j*count[j-1]
		sqsum += j**2*count[j-1]
		j += i

	ans += round(((isum**2-sqsum)/2)*w[i-1])
	ans = ans%M

print(ans)

Submission status: Wrong Answer

Solution code:
V = 1000000

# divisor
def div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

# nまでのエラストテネスの篩
def make_prime_checker(n):
    is_prime = [False, True, False, False, False, True] * (n//6+1)
    del is_prime[n+1:]
    is_prime[1:4] = False, True, True
    for i in range(5, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i::i] = [False] * (n//i-i+1)
    return is_prime

# 1からVまでの素数リスト
primes = [p for p, bool in enumerate(make_prime_checker(V)) if bool]

# define w
def w(n):
    if n == 1:
        return 1.0
    else:
        val = 1/n
        for p in primes:
            if n % p == 0:
                val *= (1 - p)
        return val


# count number
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d_num = [0] * (V + 1)
    linear = [0] * (V + 1) # linear[d] = ¥sum_{d|A_i} A_i
    quad = [0] * (V + 1) # quad[d] = ¥sum_{d|A_i} A_i^2
    for a in A:
        for d in div(a):
            d_num[d] += 1
            linear[d] += a
            quad[d] += a**2

    ans = 0
    for d in range(1, V + 1):
        if d_num[d] >= 2:
            ans += w(d) * (linear[d] ** 2 - quad[d]) // 2
            ans %= 998244353

    print(int(ans))

main()

Submission status: Wrong Answer

Solution code:
V = 1000000

# divisor
def div(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

def factor(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

# define w
def w(n):
    if n == 1:
        return 1.0
    else:
        val = 1/n
        for p, _ in factor(n): #####################################
            val *= (1 - p)
        return val


# count number
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d_num = [0] * (V + 1)
    linear = [0] * (V + 1) # linear[d] = ¥sum_{d|A_i} A_i
    quad = [0] * (V + 1) # quad[d] = ¥sum_{d|A_i} A_i^2
    for a in A:
        for d in div(a):
            d_num[d] += 1
            linear[d] += a
            quad[d] += a**2

    ans = 0
    for d in range(1, V + 1):
        if d_num[d] >= 2:
            ans += (linear[d] ** 2 - quad[d]) // 2 * w(d)
            ans %= 998244353

    print(int(ans))

main()

Submission status: Wrong Answer

Solution code:
# 解説 AC

# 参考1: https://twitter.com/rickytheta/status/1175412019006074880
# 参考2: https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-09-21agc-038

mod = 998244353
max_A = 10**6
N = int(input())
A = list(map(int, input().split()))

# nまでの自然数が素数かどうかを表すリストを返す  O(nloglogn)
def make_prime_checker(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 is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return is_prime

primes = [p for p, is_prime in enumerate(make_prime_checker(max_A)) if is_prime]  # max_A 以下の素数のリスト

g = [0] * (max_A+1)
for a in A:
    g[a] += a
for p in primes:
    # 倍数集合の高速ゼータ変換みたいなやつ  O((max_A)loglog(max_A))
    # 参考: http://noshi91.hatenablog.com/entry/2018/12/27/121649
    # 大量に約数列挙みたいなことをするときはこれで高速化できる場合が多そう？（みんぷろ 2018 本戦 A - Uncommon など）
    for k in range(max_A//p, 0, -1):
        g[k] += g[k*p]

# この時点で g[d] = Σ_{d|a} a  (A の要素のうち d の倍数であるものの総和)

g = [v * v % mod for v in g]

# この時点で
# g[d] = (Σ_{d|a} a)(Σ_{d|b} b)
#      = Σ_{(d|a)∧(d|b)} ab
#      = Σ_{d | gcd(a,b)} ab

# この式変形天才すぎないか？（これを使った一連の操作を gcd 畳み込み というらしい？）

for p in primes:
    # 倍数集合の高速メビウス変換みたいなやつ  O((max_A)loglog(max_A))

    # for k in range(1, max_A//p+1):
    #     g[k] -= g[k*p]  # 包除原理ヤバい
    
    for k, g_kp in enumerate(g[p::p]):  # 高速化（ゼータ変換の方は途中で g が変化するので高速化できない）
        g[k] -= g_kp  # 包除原理ヤバい

# この時点で g[d] = Σ_{gcd(a,b)=d} ab

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0, 1]
    for i in range(2, n+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    return modinv

modinv_list = make_modinv_list(max_A, mod)
ans = sum((gg * minv % mod for gg, minv in zip(g, modinv_list)))
ans %= mod

# この時点で
# ans = Σ_d ( Σ_{gcd(a,b)=d} ab/d )
#     = Σ_d ( Σ_{gcd(a,b)=d} lcm(a,b) )
#     = Σ_a Σ_b lcm(a,b)

ans -= sum(A)
ans *= modinv_list[2]
ans %= mod

# この時点で ans = Σ_{i<j} lcm(a,b)

print(ans)