【今日の精進】AGC038C - LCMs

毎日格上の問題を倒すやつの85日目です。

問題リンク

atcoder.jp

問題概要

数列 があるよ。

のすべてのペアの最小公倍数の和を求めてね。

解法

いわゆる約数包除です。

最大公約数が のペアを考えると、数の種類が少ないおかげでいい感じに計算できます。

それぞれのペアの積の合計を求めたいですが、これは和と二乗和を持っておけば良いです。

二乗に見えますが、(弱い)エラトステネスの篩と同じ要領でlogがつく程度で済みます。

提出コード

MAX_A=10**6
MOD=998244353
rev2=pow(2,-1,MOD)
N=int(input())
A=list(map(int,input().split()))
cnt=[0]*(MAX_A+1)
for i in A:
    cnt[i]+=1
div=[0]*(MAX_A+1)
ans=0
for i in range(1,MAX_A+1):
    use=pow(i,-1,MOD)-div[i]
    add=0
    squ=0
    for j in range(i,MAX_A+1,i):
        squ+=j*j*cnt[j]
        add+=j*cnt[j]
    ans+=use*((add*add-squ)*rev2)
    ans%=MOD
    for j in range(i,MAX_A+1,i):
        div[j]+=use
print(ans)

Submission #48481937 - AtCoder Grand Contest 038

感想

くりさんの問題もりーふさんの問題くらい引くようになってきたな