\(\text{MAX}=5\times 10^5\) とします。

まず、\(\displaystyle \sum_{i=1}^N ((x+A_i)\bmod B_i)=xN+\sum_{i=1}^N A_i-\sum_{i=1}^N B_i\left\lfloor\frac{x+A_i}{B_i} \right\rfloor\) が成り立つので、各 \(x\) に対し \(\displaystyle \sum_{i=1}^N B_i\left\lfloor\frac{x+A_i}{B_i} \right\rfloor\) を計算することができればこの問題に正答できることが分かります。以降はこの値を計算することを考えます。

\((A_i,B_i)\) の組が同じペアをまとめることで、\((a,b,r)\) で「\((A_i,B_i)=(a,b)\) を満たす \(i\) が \(r\) 個」という情報を保持することを考えます。このように圧縮した列を順に \((a_1,b_1,r_1),(a_2,b_2,r_2),\dots,(a_n,b_n,r_n)\) とします。このようにまとめると、求める値は \(\displaystyle \sum_{i=1}^n r_ib_i\left\lfloor \frac{x+a_i}{b_i}\right\rfloor\) となります。

ここで、各 \(i\) に対し \(\displaystyle \left\lfloor \frac{x+a_i}{b_i}\right\rfloor\) の値が変わる箇所は高々 \(\displaystyle \left\lceil\frac{\text{MAX}}{b_i}\right\rceil\) 箇所なので、それぞれに対し \(r_ib_i\) を加算し最後にまとめて累積和を取ることでこれらの値をまとめて計算することができます（imos 法）。

この解法は一見 \(N\times \text{MAX}\) 回計算が必要なように見えますが、実は計算回数はもっと少なく、実行時間に間に合う程度の回数しか計算しないことが証明できます。

計算回数は \(\displaystyle \sum_{i=1}^n\left(\frac{\text{MAX}}{b_i}+1\right)\) 回以下と見積もることができますが、この値が最も大きくなるのは常に \(r_i=1\) で \(b_i\) の値が小さい順に網羅されている場合です。

\(b_i=x\) となる \(a_i\) は \(x\) 通り以下なので、\(\displaystyle \sum_{i=1}^X i \geq \text{MAX}\) となる最小の \(X\) を取ることでこの計算回数は \(\displaystyle \sum_{i=1}^X i\times \left(\frac{\text{MAX}}{i}+1\right)=X\times \text{MAX}+\frac{X(X+1)}2\) 回以下であると見積もれます。\(\text{MAX}=5\times 10^5\) に対して \(X=10^3\) となることを用いると計算回数は \(500500500(\risingdotseq 5\times 10^8)\) 回以下であると見積もることができ、それぞれの計算が非常に軽いことからこの解法は実行時間制限に間に合うことが分かります。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)