题目#

BZOJ-2056

一道有点复杂的数论分块。

公式推导#

所求即为：

$\sum_{i=1}^{n}\sum_{j=1}^{m}{(n \bmod i )\cdot (m\bmod j)(i \neq j)}$

先不管 $i\neq j$ 的情况: $\sum_{i=1}^{n}(\sum_{j=1}^{m}{(n\bmod i) \cdot (m\bmod j)})$

$\sum_{i=1}^{n}\sum_{j=1}^{m}{(n-i\lfloor \frac{n}{i} \rfloor)(m-j\lfloor \frac{m}{j} \rfloor)}$

$\sum_{i=1}^{n}\sum_{j=1}^{m}{(n m - n\cdot j\lfloor \frac{m}{j} \rfloor - m\cdot i\lfloor \frac{n}{i} \rfloor + ij\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{j} \rfloor)}$

$n^2m^2 - n^2\sum_{j=1}^{m}{j\lfloor \frac{m}{j} \rfloor} - m^2\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor + \sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor\sum_{i=1}^{m}j\lfloor \frac{m}{j} \rfloor$

然后在讨论 $i = j$ 的情况:

$\sum_{i=1}^{min(n, m)}{(n\bmod i)\cdot (m\bmod i)}$

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

$\sum_{i=1}^{min(n, m)}{n m - m\cdot i\lfloor \frac{n}{i} \rfloor - n\cdot i\lfloor \frac{m}{i} \rfloor + i^2 \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor}$

然后就可以愉快的分块了。

代码#

1
/**************************************************************
2
    Problem: 2956
3
    User: Dicer
4
    Language: C++
5
    Result: Accepted
6
    Time:184 ms
7
    Memory:1292 kb
8
****************************************************************/
9

10
#include<bits/stdc++.h>
11
#define rep(i, a, b)    for(int i = (a); i <= (int)(b); ++i)
12
#define per(i, a, b)    for(int i = (a); i >= (int)(b); --i)
13
#define debug(x)    cout << #x << ' ' << x << endl;
14
using namespace std;
15

16
typedef long long ll;
17
const int MAXN = 1e5 + 7;
18
const int MOD = 19940417;
19
const int INV = 3323403;
20

21
ll cal(ll n){
22
    ll ans = 0;
23
    for(ll i = 1, j; i <= n; i = j + 1){
24
        j = n / ( n / i);
25
        ans += (i + j) * (j - i + 1) / 2 * (n / i);
26
        ans %= MOD;
27
    }
28
    return ans;
29
}
30
ll cal(ll n, ll k){
31
    ll ans = 0;
32
    for(ll i = 1, j; i <= k; i = j + 1){
33
        j = min(k, n / ( n / i));
34
        ans += (i + j) * (j - i + 1) / 2 * (n / i);
35
        ans %= MOD;
36
    }
37
    return ans;
38
}
39

40
ll sum(ll n){
41
    return n * (n + 1) % MOD * (2 * n + 1) % MOD * INV % MOD;
42
}
43

44
ll cal(ll n, ll m, ll k){
45
    ll ans = 0;
46
    for(ll i = 1, j; i <= k; i = j + 1){
47
        j = min(k, min(n / (n / i), m / (m / i)));
48
        ans += (sum(j) - sum(i-1)) * (n/i) % MOD * (m/i) % MOD;
49
        ans %= MOD;
50
    }
51
    return ans;
52
}
53

54
ll mul(ll a, ll b){
55
    a %= MOD; b %= MOD;
56
    return a * b % MOD;
57
}
58

59
int main(){
60
    ll n, m, k;
61
    scanf("%lld%lld", &n, &m);
62
    k = min(n, m);
63
    long long ans = 0;
64
    ans += mul(n * n, m * m);
65
    ans -= mul(n * n, cal(m));
66
    ans -= mul(m * m, cal(n));
67
    ans += mul(cal(n), cal(m));
68
    ans = ((ans % MOD) + MOD) % MOD;
69
    ans -= mul(k, n * m);
70
    ans += mul(n, cal(m, k));
71
    ans += mul(m, cal(n, k));
72
    ans -= cal(n, m, k);
73
    ans = ((ans % MOD) + MOD) % MOD;
74
    printf("%lld\n", ans);
75
    return 0;
76
}