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:
# 解説 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 = sorted(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], 1):  # 高速化（ゼータ変換の方は途中で 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)

Submission status: Time Limit Exceeded

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], 1):  # 高速化（ゼータ変換の方は途中で 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)

Submission status: Time Limit Exceeded

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]  # 包除原理ヤバい

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

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        modinv[i] = 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)

Submission status: Time Limit Exceeded

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]  # 包除原理ヤバい

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

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        q, r = divmod(mod, i)
        modinv[i] = mod - q * modinv[r] % 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)

Submission status: Time Limit Exceeded

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]  # 包除原理ヤバい

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

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0] * (n+1)
    modinv[1] = 1
    for i in range(2, n+1):
        modinv[i] = 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)

Submission status: Time Limit Exceeded

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

import sys
input = sys.stdin.readline
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]  # 包除原理ヤバい

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

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

modinv_list = make_modinv_list(max_A, mod)
ans = sum(gg * minv 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)

Submission status: Time Limit Exceeded

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]

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]  # 包除原理ヤバい

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

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

modinv_list = make_modinv_list(max_A, mod)
ans = sum(gg * minv 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)

Submission status: Time Limit Exceeded

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

is_prime = make_prime_checker(max_A)

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

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

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

modinv_list = make_modinv_list(max_A)
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)

Submission status: Time Limit Exceeded

Solution code:
P = 998244353
N = int(input())
A = [int(a) for a in input().split()]
V = max(A) + 1
X = [0] * V
for a in A:
    X[a] += 1

fa = [1]
for i in range(1, V):
    fa.append(fa[-1]*i%P)
fainv = [pow(fa[-1], P-2, P)]
for i in range(1, V)[::-1]:
    fainv.append(fainv[-1]*i%P)
fainv = fainv[::-1]
W = [1] + [fainv[i] * fa[i-1] % P for i in range(1, V)]

for k in range(1, V):
    for i in range(k*2, V, k):
        W[i] = (W[i] - W[k]) % P

ans = 0
for k in range(1, V):
    s1 = 0
    s2 = 0
    for i in range(k, V, k):
        if X[i]:
            s1 += i * X[i]
            s2 += i * i * X[i]
    ans = (ans + (s1*s1-s2) * W[k]) % P
print(ans * fainv[2] % P)

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-1):
    for j in range(i+1, n):
        s += a[i] * a[j] // fractions.gcd(a[i], a[j])

print(s % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

    ans = 0

    for i in range(N):
        for j in range(i + 1, N):
            g = gcd(A[i], A[j])
            l = A[i] * A[j] // g
            # print("GCD: {}".format(g))
            # print("LCM: {}".format(l))
            ans += l
            ans %= 998244353

    print(ans)


if __name__ == '__main__':
    p_c()

Submission status: Time Limit Exceeded

Solution code:
#AGC C
import fractions
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=(s+(a[i]*(a[j]//fractions.gcd(a[i],a[j])))%998244353)%998244353
print(s)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np

inFile = ''
#inFile = 'test4.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 int(x)*int(y)/z

def mondai(N, List):
    s = [np.mod(np.sum([kobai(List[i],List[j]) for j in range(i+1,N)]), 998244353) for i in range(0,N-1)]
    #print(s)
    ret = np.mod(np.sum(s),998244353)
    return int(ret)
    #return int(np.sum([np.sum([kobai(List[i],List[j]) for j in range(i+1,N)]) % 998244353 for i in range(0,N-1)]) % 998244353)
    

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

ans = mondai(N, List)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import fractions

def lcm(x):
  return (x[0] * x[1]) // fractions.gcd(x[0], x[1])

n = int(input())
A =list(map(int,input().split(' ')))

for_map = list(itertools.combinations(A, 2))

ans = sum(list(map(lcm, for_map)))
mod = ans % 998244353
print(mod)

Submission status: Time Limit Exceeded

Solution code:
import fractions
 
n = int(input())
a = [int(num) for num in input().split(' ')]
 
def lcm(x, y):
  x = x  % 998244353
  y = y  % 998244353
  return (x * y) // fractions.gcd(x, y)
 
ans = 0
for i in range(len(a) -1):
  for j in range(i+1, len(a)):
    tmp = lcm(a[i], a[j])
    ans += tmp % 998244353
 
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

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

@lru_cache(maxsize=None)
def goukei(i,j):
    if j < n-1:
        return lcm(A[i],A[j]) + goukei(i,j+1)
    else:
        return lcm(A[i],A[j])

i=n-2
while i >= 0:
    res += goukei(i,i+1)
    i-=1
#for i in range(n-1):
    #res += goukei(i,i+1)
#for a, b in com:
    #res += lcm(a,b)

print(res % waru)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

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

@lru_cache(maxsize=None)
def goukei(i,j):
    if j < n-1:
        return lcm(A[i],A[j]) + goukei(i,j+1)
    else:
        return lcm(A[i],A[j])

for i in range(n-1):
    res += goukei(i,i+1)
#for a, b in com:
    #res += lcm(a,b)

print(res % waru)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
As = [int(i) for i in input().split()]
from fractions import gcd
ans=0
for i in range(N-1):
    for j in range(i+1, N):
        a = As[i]
        b = As[j]
        ans += (a*b) // gcd(a,b)
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 998244353

N = int(readline())
A = np.array(readline().split(),np.int32)

U = 10**6+100
counter = np.bincount(A,minlength=U)

def cumprod(arr):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

x = np.arange(U,dtype=np.int64); x[0] = 1
fact = cumprod(x)
x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod(x)[::-1]

inv = np.zeros(U,dtype=np.int64)
inv[1:] = fact[:-1] * fact_inv[1:] % MOD

"""
・f(n) = sum_{gcd(a,b) == 1}ab
・g(n) = sum_{n|gcd(a,b)}ab
"""

"""
・S(n) = sum_{n|a} a
・T(n) = sum_{n|a} a^2
"""

x = np.arange(U,dtype=np.int64)*counter%MOD
y = np.arange(U,dtype=np.int64)**2%MOD*counter%MOD
S = np.zeros(U,dtype=np.int64)
T = np.zeros(U,dtype=np.int64)
M = int(U**.5+1)+10
for d in range(1,M):
    S[d] = (x[d::d]).sum()
    T[d] = (y[d::d]).sum()
for d in range(1,M):
    S[M:(U-1)//d+1] += x[M*d:U:d]
    T[M:(U-1)//d+1] += y[M*d:U:d]
S%=MOD
T%=MOD

G = (S*S-T)%MOD*inv[2]%MOD

for n in range(U-1,0,-1):
    G[n] -= G[2*n:U:n].sum()
    G[n] %= MOD

answer = (G*inv%MOD).sum()%MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())
a = [int(num) for num in input().split(' ')]

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

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

print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
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):
        lcm += (n[i] * n[j]) // fractions.gcd(n[i], n[j])
s = lcm% 998244353
print(s)

Submission status: Time Limit Exceeded

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

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

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

c = 0

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

print(c%998244353)

Submission status: Time Limit Exceeded

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

import sys
import numpy as np

inFile = ''
#inFile = 'test4.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 int(x)*int(y)/z

def mondai(N, List):
    s = [np.sum([kobai(List[i],List[j]) for j in range(i+1,N)]) % 998244353 for i in range(0,N-1)]
    #print(s)
    ret = np.sum(s)
    return int(ret % 998244353)
    #return int(np.sum([np.sum([kobai(List[i],List[j]) for j in range(i+1,N)]) % 998244353 for i in range(0,N-1)]) % 998244353)
    

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

ans = mondai(N, List)

print(ans)

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:
#a,bの最大公約数
def gcd(a, b):
  if b > a:
    tmp = a
    a = b
    b = tmp
    
  while b:
    a, b = b, a % b
  return a
 
#a,bの最小公倍数
def lcm(a, b):
  if b % a == 0:
    return b
  elif a % b == 0:
    return a

  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:
import fractions as fra
num = int(input())
number = list(map(int,input().split()))

def lcm(x, y):
    return (x * y) // fra.gcd(x, y)
cnt = 0
for i in range(0,num-1):
    for j in range(i+1,num):
        cnt = lcm(number[i], number[j]) + cnt
print(cnt%998244353)

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]))
    
print(count % 998244353)

Submission status: Time Limit Exceeded

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

def lcm(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 += lcm(A[i],A[j])
        
        
S = S % 998244353
print(S)

Submission status: Time Limit Exceeded

Solution code:
import fractions
n = int(input())
l = list(map(int, input().split(' ')))

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

total = 0
for i in range(n-1):
  for j in range(i+1, n):
    total += lcm(l[i], l[j]) 

print(total%998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
SIZE=1000003; MOD=998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
inv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

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

num = [0]*SIZE
db = [0]*SIZE
for i in a:
    num[i] += i
    db[i] += i*i
    db[i] %= MOD

def zeta(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(n//p,0,-1):
                sieve[k*p] = False
                a[k] += a[k*p]
                a[k] %= MOD
    return a


def meb(a,n):
    sieve = [True]*(n+1)
    for p in range(2,n):
        if sieve[p]:
            for k in range(1,n):
                if k*p >= n: break
                sieve[k*p] = False
                a[k] -= a[k*p] 
                a[k] %= MOD
    return a


#n = 1000000

n = 1000001

#zn = [i*i for i in zeta(num,n)]
#zdb = zeta(db,n)
#print(zn[:20])
#print(zdb[:20])

zn = [i*i for i in zeta(num,n)]
zdb = zeta(db,n)
ans = [i-j for i,j in zip(zn, zdb)]

#ans = [i*i-j for i,j in zip(zeta(num,n), zeta(db,n))]

#print(ans[:20])
#print(meb(ans,n)[:20])

res = 0
for i,c in enumerate(meb(ans,n)):
    res = (res + c*inv[i])%MOD
        
print(res*inv[2]%MOD)

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(a, b):
	return a * b // gcd (a, b)

sum = 0
for i in range(n):
  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())
nums = [int(s) for s in input().split()]
point = 0
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

for i in range(n - 1):
  for j in range(1,n - i):
  	point += lcm(nums[i],nums[i + j])
    
print(point % 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):
  if b % a == 0:
    return 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:
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a
    

def lcm(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 += lcm(A[i],A[j])
        S = S % 998244353
        

print(S)

Submission status: Time Limit Exceeded

Solution code:
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 = n[i]
        b = n[j]
       
        lcm += (a * b) // fractions.gcd(a, b)

print(lcm % 998244353)