Problem p02905 (python)

Fixed submission:
# coding: utf-8
# Your code here!
SIZE=1000001; 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]*1000001
db = [0]*1000001
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 = 1000000

#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+1)):
    res = (res + c*inv[i])%MOD
        
print(res*inv[2]%MOD)

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

#aを破壊的にgcd-zetaする
def zeta_gcd(a):
    n = len(a)-1
    seive = [True]*(n+1)
    for p in range(2,n):
        if seive[p]:
            for i in range(n//p,0,-1):
                seive[p*i] = False
                a[i] += a[p*i]
                a[i] %= MOD
#    return a

#aを破壊的にgcd-mobiusする
def mobius_gcd(a):
    n = len(a)
    seive = [True]*(n+1)
    for p in range(2,n):
        if seive[p]:
            for i in range(1,n):
                if i*p >= n: break
                seive[p*i] = False
                a[i] -= a[p*i] 
                a[i] %= MOD
#    return a

################################################

#################################################

SIZE=1000001; 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
for i in a: num[i] += i

assert n != 3

zeta_gcd(num)
ans = [i*i for i in num]
mobius_gcd(ans)

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

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

#aを破壊的にgcd-zetaする
def zeta_gcd(a):
    n = len(a)-1
    seive = [True]*(n+1)
    for p in range(1,n):
        if seive[p]:
            for i in range(n//p,0,-1):
                a[i] += a[p*i]
                a[i] %= MOD
#    return a

#aを破壊的にgcd-mobiusする
def mobius_gcd(a):
    n = len(a)
    seive = [True]*(n+1)
    for p in range(1,n):
        if seive[p]:
            for i in range(1,n):
                if i*p >= n: break
                a[i] -= a[p*i] 
                a[i] %= MOD
#    return a

################################################

#################################################

SIZE=1000001; 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
for i in a: num[i] += i

assert n != 3

zeta_gcd(num)
ans = [i*i for i in num]
mobius_gcd(ans)

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

Buggy submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
def Eratosthenes(N): #N以下の素数のリストを返す
    #iが素数のときis_prime_list[i]=1，それ以外は0
    N+=1
    is_prime_list = [True]*N
    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]

#aを破壊的にgcd-zetaする
def zeta_gcd(a):
    n = len(a)-1
    seive = [True]*(n+1)
    for p in range(1,n):
        if seive[p]:
            for i in range(n//p,0,-1):
                a[i] += a[p*i]
                a[i] %= MOD
#    return a

#aを破壊的にgcd-mobiusする
def mobius_gcd(a,primes):
    n = len(a)
    seive = [True]*(n+1)
    for p in range(1,n):
        if seive[p]:
            for i in range(1,n):
                if i*p >= n: break
                a[i] -= a[p*i] 
                a[i] %= MOD
#    return a

################################################

#################################################

SIZE=1000001; 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
for i in a: num[i] += i

assert n != 3

zeta_gcd(num)
ans = [i*i for i in num]
mobius_gcd(ans)

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