清华集训2012 [模积和]

题解

---

question

求

$$\sum_{i=1}^{j=n} \sum_{j=1}^{j=m}(n \bmod i)(m \bmod j),i \ne j$$

solve

$$\sum_{i=1}^{n} \sum_{j=1}^{m}(n \bmod i)(m \bmod j),i \ne j$$
$$原式 = \sum_{i=1}^{n} (n - \lfloor \frac{n}{i} \rfloor i) \sum_{j=1}^{m} (m - \lfloor \frac{m}{i} \rfloor i) - \sum_{i=1}^{min(n,m)}(n - \lfloor \frac{n}{i} \rfloor i)(m - \lfloor \frac{m}{i} \rfloor i)\\ =\sum_{i=1}^{n} (n - \lfloor \frac{n}{i} \rfloor i) \sum_{j=1}^{m} (m - \lfloor \frac{m}{i} \rfloor i) - \\ \sum_{i=1}^{min(n,m)}(nm - m \lfloor \frac{n}{i} \rfloor i - n \lfloor \frac{m}{i} \rfloor i + \lfloor \frac{m}{i} \rfloor \lfloor \frac{n}{i} \rfloor i^2)$$

数论分块
时间复杂度 $O(\sqrt(n) + \sqrt(m))$

Code

#include <bits/stdc++.h>
#define LL long long
const LL Mod = 19940417, Inv = (Mod + 1) / 6;
LL n, m, Answer, Answer_1, Answer_2, Answer_3;
LL Calc(LL x) {return x * (x + 1) % Mod * (2 * x + 1) % Mod * Inv % Mod;}
LL Calc_2(LL l, LL r) {return (l + r) * (r - l + 1) / 2 % Mod;}
int main() {
    std:: cin >> n >> m;
    if(n > m) std:: swap(n, m);
    for(int i = 1, r; i <= n; i = r + 1) {
        r = n / (n / i);
        Answer_1 = (Answer_1 + (Calc_2(i, r) * (n / i) % Mod)) % Mod;
    }
    Answer_1 = (n * n - Answer_1);
    Answer_1 %= Mod;
    for(int i = 1, r; i <= m; i = r + 1) {
        r = m / (m / i);
        Answer_2 = (Answer_2 + (Calc_2(i, r) * (m / i) % Mod)) % Mod;
    }
    Answer_2 = (m * m - Answer_2) % Mod;
    for(int i = 1, r; i <= n; i = r + 1) {
        r = std:: min(n / (n / i), m / (m / i));
        LL imp = n * m % Mod * (r - i + 1) % Mod;
        imp = (imp + (- (m * (n / i) + n * (m / i)) % Mod * Calc_2(i, r) % Mod)) % Mod;
        imp = (imp + n / i * (m / i) % Mod * (Calc(r) - Calc(i - 1)) % Mod) % Mod;
        Answer_3 = (Answer_3 + imp) % Mod;
    }
    Answer = Answer_1 * Answer_2 % Mod;
    Answer -= Answer_3;
    Answer %= Mod;
    if(Answer < 0) Answer += Mod;
    std:: cout << Answer;
    return 0;
}