考察
要求はi=1,…,N、j=1,…,Mの全組のA_iB_j(i mod j)。i<jも含まれ、その場合i mod j=iである。固定jで商k=floor(i/j)が一定なら、剰余はi−jkという一次式になる。
PA[t]=Σ_{i=1}^t A_i、PIA[t]=Σ_{i=1}^t iA_i、PA[0]=PIA[0]=0を用意する。各j=1,…,Mについて、まず商0の区間[1,min(N,j−1)]からB_j·PIA[min(N,j−1)]を足す。次にk=1,…,floor(N/j)についてl=jk、r=min(N,j(k+1)−1)とし、
B_j·((PIA[r]−PIA[l−1])−jk(PA[r]−PA[l−1]))
を足す。全演算をmod 998244353で行う。j>Nなら商0の項だけであり、N≠Mでも同じ手順で全組を覆う。
例えばN=1,M=2,A=(1),B=(1,1)ではj=1の寄与0、j=2の商0の寄与1なので答え1。商1以上だけを走査するとこの最小反例を落とす。
全pair列挙はO(NM)だが、商0は各jで定数時間、残りのblock数はΣ_{j≤min(M,N)}floor(N/j)=O(N log N)。剰余を商一定区間へ分け、二つの重み付きprefix和から区間総和を計算すればO(N log N+M)になる。
典型の発動条件
商一定区間の分割
発動条件: floor(i/j) や i mod j を全 pair で総和したいとき。
固定 divisor ごとに quotient が一定の連続区間を走査する。
重み付き prefix sum
発動条件: 区間内で係数が index の一次式になる総和を求めたいとき。
ΣA_i と ΣiA_i を組み合わせる。
問題固有の要素
mod を不規則な値として扱わず、quotient ごとの一次式へほどくと区間集約できる。
別の問題へ持ち帰る視点: 二重 loop でも内側長が N/j なら、総計を調和級数で評価して採用可能性を判断する。
正当性
各jの商0区間は[1,min(N,j−1)]、正の商kの区間は[jk,min(N,j(k+1)−1)]で、互いに素かつi=1,…,Nを覆う。商0ではi mod j=i、それ以外ではi−jkなので、提示したprefix差が各区間の重み付き剰余和を与える。全j=1,…,Mの寄与を足せば要求する全ordered pairを一度ずつ数える。
実装上の注意
- NはAの長さ、MはBの長さ。jをMまで走査し、j>Nでは商0だけを加える。
- PA[0]=PIA[0]=0、商0の右端min(N,j−1)を使う。商1以上のbucketへ重ねない。
- 各積は64 bitで中間計算し、prefix差と最終値をmod 998244353で正規化する。
復習の核
- 一つの j で quotient block を列挙し、i mod j=i-jk の区間寄与式と全 block 数の調和級数評価を手で導く。
計算量と制約
時間
O(N log N+M)。二つのweighted prefix和で各商bucketを定数時間評価する。
空間
O(N+M)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N,M \leq 5 \times 10^5; 1 \leq A_i, B_j \leq 5 \times 10^5; All input values are integers.
出典