象棋与马

Posted on Edited on In Word count in article: 1.5k Reading time ≈ 5 mins.
莫比乌斯反演经典题目

题意

有一个马最开始在 \((0,0)\)，它的每一步可以走一个 \(a\times b\) 的矩形（ 即能够从 \((x,y)\) 到达 \((x\pm a,y\pm b)\) 或 \((x\pm b,y\pm a)\) ）。

若马通过上述移动方式可以到达棋盘中任意一个点，那么 \(p(a,b)=1\)，否则 \(p(a,b)=0\)。

给你 \(T\) 组询问，每组给你一个 \(n\)，让你求： \[ \left(\sum_{a=1}^n\sum_{b=1}^np(a,b)\right)\mod {2^{64}} \]

分析

首先，本质不同的行走方案有四种，即 \((a,b),(b,a),(-a,b),(-b,a)\)，那么设这四种本质不同的分别走了 \(x_1,x_2,x_3,x_4\) 次，那么能够走满这个棋盘的充要条件是： \[ \begin{cases} ax_1+bx_2-ax_3-bx_4=1\\ bx_1+ax_2+bx_3+ax_4=0 \end{cases} \] 只要满足了这个条件，它就可以上下左右移动了，就是说可以走满整张棋盘

那么可以化简一下上式，然后得到： \[ \begin{aligned} &a((x_1+x_2)-(x_3-x_4))+b((x_1+x_2)+(x_3-x_4))=1\\ \therefore &a(x-y)+b(x+y)=1 \end{aligned} \] 那么此时可以得到两条性质：

  • \(a\perp b\)
  • \(a\not\equiv b\pmod 2\)

第一条的话，就是因为 \(akx+bky=k\gcd(a,b)\)；第二个的话，就是说 \(x-y\) 和 \(x+y\) 一定是奇偶性相同的而且只能是奇数，那么 \(a、b\) 一定一奇一偶，正确性显然

所以可以得到 \(p(a,b)=[a\perp b]\land a,b\)奇偶性不相同

算法一

既然已经知道了 \(a、b\) 奇偶性不同，那么就可以限制谁是奇数谁是偶数，最后 \(\times2\) 就可以

时间复杂度 \(O(n^2)\)，期望得分 \(20\)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>

int n, t;

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    scanf ("%d", &t);
    while (t--) {
        int ans(0);
        scanf ("%d", &n);
        for (int i = 1; i <= n; i += 2)
            for (int j = 2; j <= n; j += 2) 
                if (gcd(i, j) == 1) ++ans;
        printf("%d\n", ans * 2);
    }
}

算法二

根据算法一，我们知道题目限制了两个数的奇偶性，那么我们先试着表达一下，再看看可以怎么化简 \[ \sum_{a=1}^n\sum_{b=1}^np(a,b)=2\times\sum_{a=1}^n\sum_{b=1}^n[a\perp b\text{且a为偶数b为奇数}] \] 又因为 \(a\perp b\) 且 \(a\) 是偶数 \(b\) 是奇数，那么 \(a\rightarrow \frac a2\)，也是可以得到 \(a\perp b\) 的

所以又得到了 \[ \begin{aligned} \sum_{a=1}^n\sum_{b=1}^n[a\perp b\text{且a为偶数b为奇数}]&=\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b\text{且b为奇数}]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^n[a\perp b\text{且b是偶数}] \end{aligned} \] 感觉这个容斥还是很好想到的，那么就可以继续往下走，定义记号 \(f(n,m)\) \[ \begin{aligned} f(n,m)&=\sum_{a=1}^n\sum_{b=1}^m[a\perp b\text{且a为偶数b为奇数}]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b\text{且b是偶数}]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b\text{且a是奇数b是偶数}]\\ &=\sum_{a=1}^{\frac n2}\sum_{b=1}^m[a\perp b]-f(m,\frac n2) \end{aligned} \] 为了方便表述，就令 \[ \begin{aligned} s(n,m)&=\sum_{a=1}^n\sum_{b=1}^m[a\perp b]\\ &=\sum_{a=1}^n\sum_{b=1}^m\sum_{d|\gcd(a,b)}\mu(d)\\ &=\sum_{d=1}^{\min(a,b)}\mu(d)\left\lfloor\frac nd\right\rfloor\left\lfloor\frac md\right\rfloor \end{aligned} \] 所以 \(f(n,m)=s(\frac n2,m)-f(m,\frac n2)\)

然后 \(s\) 的计算可以数论分块，\(f\) 递归计算，所以时间复杂度为 \(O(\log n\sqrt n)\)

Code

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
53
54
55
56
57
58
59
60
61
62
63
#include <cstdio>
#include <algorithm>

using namespace std;

typedef unsigned long long ll;
const int maxn = 1e7 + 10;
int n, t, cnt;
ll mu[maxn];
int p[maxn];
bool vis[maxn];

inline void init()
{
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < maxn; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else break;
        }
    }

    for (int i = 1; i < maxn; ++i) mu[i] += mu[i - 1];
}

inline int min(int x, int y)
{
    if (x < y) return x;
    return y;
}

ll solve(int n, int m) 
{
    ll sum(0);
    if (n > m) swap(n, m);
    for (int l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        sum += (mu[r] - mu[l - 1]) * (n / l) * (m / l);
    }
    return sum;
}

ll gc(int n, int m)
{
    if (m == 1) return 0;
    if (n == 1) return m / 2;
    ll total = solve(n, m / 2), cut = gc(m / 2, n);
    return total - cut;
}

int main()
{
    init();
    scanf ("%d", &t);
    while (t--) {
        scanf ("%d", &n);
        ll total = solve(n / 2, n), cut = gc(n / 2, n);
        ll ans = (total - cut) * 2;
        printf ("%llu\n", ans);
    }
}

满分做法

算法二的瓶颈在于空间，开不了 \(10^{11}\) 的数组，所以考虑使用杜教筛，就可以过题了

至于这个的时间复杂的的话，个人感觉是 \(O(\log n\sqrt n+n^{\frac 32})\)，不知道对不对

希望有大佬能告诉我正确的时间复杂度

Code

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <cstdio>
#include <map>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;
const int maxn = 1e7 + 10;
ll n, t, cnt;
ull mu[maxn];
int p[maxn];
bool vis[maxn];

inline void init()
{
    mu[1] = 1;
    for (int i = 2; i < maxn; ++i) {
        if (!vis[i]) p[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * p[j] < maxn; ++j) {
            vis[i * p[j]] = 1;
            if (i % p[j]) mu[i * p[j]] = -mu[i];
            else break;
        }
    }

    for (int i = 1; i < maxn; ++i) mu[i] += mu[i - 1];
}

inline ll min(ll x, ll y)
{
    if (x < y) return x;
    return y;
}

map <ll, ull> Mu;

ull MMu(ll x)
{
    if (x <= maxn) return mu[x];
    if (Mu[x]) return Mu[x];
    ll Ans(1);
    for (ll l(2), r; l <= x; l = r + 1)
    {
        r = x / (x / l);
        Ans -= (r - l + 1) * MMu(x / l);
    }
    return Mu[x] = Ans;
}

ull solve(ll n, ll m) 
{
    ull sum(0);
    if (n > m) swap(n, m);
    for (ll l = 1, r; l <= n; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        sum += (MMu(r) - MMu(l - 1)) * (n / l) * (m / l);
    }
    return sum;
}

ull gc(ll n, ll m)
{
    if (m == 1) return n / 2;
    if (n == 1) return 0;
    ull total = solve(n / 2, m), cut = gc(m, n / 2);
    return total - cut;
}

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int main()
{
    init();
    t = __read();
    while (t--) {
        n = __read();
        ull ans = gc(n, n) * 2;
        printf ("%llu\n", ans);
    }
}