洛谷 P5348 密码解锁

发表于

着实被这个题恶心到了一小下，玄学复杂度不解释。

Description

点我进入题目

你有一个长度为 $n$ 的数组 $a_n$，你并不知道 $a_n$ 具体是什么，但是你知道对于 $\forall d \leq n$，满足 $\sum\limits_{i = 1}^{\frac nd}a_{id} = \mu(d)$，问你 $a_m$ 的值。

(以上包括以下的除法皆为向下取整)。

Solution

一看到成倍数的容斥就直接上 $\mu$ 函数就可以了，如果你对这个并不了解我们可以这样处理。

我们设 $f(n) = a_n$，显然有：

$$ f(m) = \sum_{i = 1}^{\frac nm}f(im)[i == 1] $$

$$ = \sum_{i = 1}^{\frac nm} f(im)\sum_{d|i}\mu(d)$$

$$ = \sum_{d = 1}^{\frac nm}\mu(d)\sum_{i = 1}^{\frac n{md}}f(imd) $$

$$ = \sum_{d = 1}^{\frac nm}\mu(d)\mu(md) $$

然后我们考虑如何求这一个东西，对于函数 $\mu$，我们有

$$ \mu(md) = \mu(m)\mu(d)[(m,d) = 1] $$

其中 $(m,d)$ 代表 $m$ 和 $d$ 的最大公约数。

那么我们直接替换 $\mu(md)$ 可以得到：

$$ f(m) = \mu(m)\sum_{d = 1}^{\frac nm}\mu(d)^2[(m,d) = 1]$$

那么我们现在就要求后边这一坨东西，我们首先能想到的是只要 $\mu(d) = 1$ 的充要条件是 $d$ 不包含平方数因子，那么我们可以枚举所有的平方数因子进行容斥，这样只需要枚举到根号即可，具体地，我们设 $t = \frac nm$，$st = \sqrt{t}$。

$$ f(m) = \mu(m)\sum_{i = 1}^{st}\mu(i)\sum_{j = 1}^{\frac t{i^2}}[(i^2j,m)=1] $$

在这里我们的 $i^2$ 就是我们枚举的平方数因子，$\mu(i)$ 是容斥的系数，后边的 $i^2j$ 枚举的就是含有 $i^2$ 作为因子的每一个数。

那么我们可以熟练地对后边的那一坨进行莫比乌斯反演的套路操作，转化为：

$$ f(m) = \mu(m)\sum_{i = 1}^{st}\mu(i)\sum_{d|m}\mu(d)\frac t{i^2d} $$

然后这个东西我们是可以直接计算的，事先处理好 $m$ 的每个因数 $d$ 与 $\mu(d)$ 的值，然后进行复杂度为 $O(\alpha\sqrt \frac nm)$ 的计算，在这里 $\alpha$ 指 $m$ 的因数个数，据统计再 $1 \leq m \leq 10^9$ 的条件下这个 $\alpha$ 最大为 $1300$ 左右，足够通过本题。

Demonstration

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
#include <bits/stdc++.h>

typedef long long ll;

const int MAXN = 1e6 + 6;

int mu[MAXN], notprime[MAXN], prime[MAXN], cnt = 0;

void Shaker(int n) {
    mu[1] = 1;
    notprime[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!notprime[i]) prime[cnt++] = i, mu[i] = -1;
        for(int j = 0; j < cnt && prime[j] * i <= n; j++) {
            notprime[i * prime[j]] = 1;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = -mu[i];
        }
    }
    cnt = 0;
}

ll Mu(ll n) {
    if(n < MAXN) return mu[n];
    ll res = 1;
    for(ll i = 2; i * i <= n; i++) {
        if(n % i != 0) continue;
        n /= i, res = -res;
        if(n % i == 0) return 0;
    }
    if(n > 1) res = -res;
    return res;
}

ll gcd(ll a, ll b) {
    return b ? gcd(b, a % b) : a;
}

ll dv[MAXN], dm[MAXN];

ll g(ll n, ll m) {
    ll res = 0;
    for(int i = 0; i < cnt; i++) {
        ll d = dv[i];
        res = res + dm[i] * (n / d);
    }
    return res;
}

ll f(ll n, ll m) {
    ll res = 0, t = n / m, st = sqrt(t);
    cnt = 0;
    for(ll d = 1; d * d <= m; d++) {
        if(m % d != 0) continue;
        dv[cnt] = d, dm[cnt++] = Mu(d);
        ll d2 = m / d;
        if(d2 == d) continue;
        dv[cnt] = d2, dm[cnt++] = Mu(d2);
    }
    for(ll i = 1; i <= st; i++) {
        if(gcd(i, m) == 1) res = res + Mu(i) * g(t / i / i, m);
    }
    return Mu(m) * res;
}

int main() {
    int T;
    scanf("%d", &T);
    Shaker(MAXN - 1);
    while(T--) {
        ll n, m;
        scanf("%lld%lld", &n, &m);
        printf("%lld\n", f(n, m));
    }
    return 0;
}