codevs1999 模积和

发表于

codevs 1999 模积和

题目不是很难，但取模比较繁琐，为此 WA 了两遍。

题目大意

求：
$$ \sum_{1 \leq i \leq n & 1 \leq j \leq m & i \neq j} (n % i)(m % j) $$

设 $t = \min(n, m)$
一步步向下推：

设 $f(t, n) = \sum\limits_{i = 1}^t(n % i)$

$$ \sum_{1 \leq i \leq n & 1 \leq j \leq m & i \neq j} (n % i)(m % j) $$

$$ = f(n, n)\times f(m, m) - \sum_{i = 1}^{t}(n % i)(m % i) $$

$$ f(t, n) = \sum_{i = 1}^t(n - i\lfloor\frac{n}i\rfloor) $$

$$ = tn - \sum_{i = 1}^ti\lfloor\frac{n}i\rfloor $$

由于 $\lfloor\frac{n}i\rfloor$ 只有约 $\sqrt n$ 种取值，我们可以在 $O(\sqrt n)$ 内求出。

对于 $\sum\limits_{i = 1}^{t}(n % i)(m % i)$ 一样处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <cstdio>
#include <algorithm>
#define MOD 19940417LL

int n, m;

int solve_single(int t, int n) {
    int res = 0;
    for(int l = 1; l <= t; l++) {
        int r = n / (n / l);
        if(r > t) r = t;
        res = (res + ((1LL * (r - l + 1) * (l + r) / 2) % MOD) * (n / l)) % MOD;
        l = r;
    }
    return res;
}

inline int GetSum(int n) {
    int res = 1LL * n * (n + 1) % MOD;
    res = 1LL * res * (2 * n + 1) % MOD;
    res = 1LL * res * 3323403 % MOD;
    return res;
}

int solve_double(int t) {
    int res = 0;
    for(int l = 1; l <= t; l++) {
        int r = std::min(n / (n / l), m / (m / l)); 
        if(r > t) r = t;
        res = (res + (1LL * (GetSum(r) - GetSum(l - 1)) * (n / l) % MOD) * (m / l)) % MOD;
        l = r;
    }
    return res;
}

int solve() {
    int res = 0, t = std::min(n, m);
    res = (res + 1LL * n * n - solve_single(n, n)) % MOD;
    res = (1LL * res * (1LL * m * m % MOD - solve_single(m, m))) % MOD;
    res = (res - (1LL * t * n % MOD) * m) % MOD;
    res = (res + 1LL * n * solve_single(t, m)) % MOD;
    res = (res + 1LL * m * solve_single(t, n)) % MOD;
    res = (res - solve_double(t)) % MOD;
    if(res < 0) res += MOD;
    return res;
}

int main(int argc, char *argv[]) {
    scanf("%d%d", &n, &m);
    printf("%d", solve());
    return 0;
}