[Mivik Round / 梦境彼岸] [题解] 彼岸 The Next Part of the Dream
Mivik
·
·
题解
Subtask 1
给暴力分是中华民族的优秀传统美德。
Subtask 2
我们注意到这个子任务给了很多分，暗示着出题人认为会了求单点就差不多会做了（嗯嗯）。
保留题目中 1 开始的下标机制，我们发现洗一次牌本质上就是进行一次
k\rightarrow 2k\pmod{2^n+1}
的置换（记为 P）。而题目中的 f(n) 实际上就是在对 P^0,P^1,P^2,\dots,P^{n-1} 这些置换的不动点个数求和。
不妨先来研究一下这个置换的环。首先有个显然的观察：环长最大是 2n。因为对于任何整数 t（1\le t\le\left(2^n+1\right)），我们有
\begin{aligned}
&2^{2n}t\\
=&\left(2^{2n}-1\right)t+t\\
=&\left(2^n-1\right)\left(2^n+1\right)t+t\\
=&t\pmod{2^n+1}
\end{aligned}
我们想要求出长度为 k 的环有多少个，可直接切入似乎会没有什么思路。我们考虑计算所在环长度为 k 的约数的数的个数 B_k，然后就可以莫比乌斯反演得到所在环长度为 k 的数的个数 A_k。
我们发现，对于一个数 t，它在一个长度为 k 的约数的环内，当且仅当
\begin{aligned}
2^kt&\equiv t\pmod{2^n+1}\\
\left(2^k-1\right)t&\equiv 0\pmod{2^n+1}
\end{aligned}
即
\begin{aligned}
(2^n+1)&\mid \left((2^k-1)t\right)\\
\frac{2^n+1}{\left(2^n+1,2^k-1\right)}&\mid t
\end{aligned}
> 定理一：对于 $n,m,a\in\Z^+$，有
>
$$
\left(a^n-1,a^m-1\right)=a^{(n,m)}-1
$$
关于这个定理的一个（甚至更通用的证明）可以看 [这里](https://math.stackexchange.com/questions/7473/prove-that-gcdan-1-am-1-a-gcdn-m-1)。
可是上面的是 $\left(2^n+1,2^k-1\right)$，看起来似乎没什么联系啊？
我们不妨改写为
$$
\left(2^n+1,2^k-1\right)=\left(\frac{2^{2n}-1}{2^n-1},2^k-1\right)
$$
然后我们知道
> 定理二：对于 $p,q,k\in\Z^+,(p,q)=1$，有
>
$$
(k,p)=\frac{(k,pq)}{(k,q)}
$$
这个挺显然的。由于 $(2^n-1,2^n+1)=(2^n-1,2)=1$，于是就有
$$
\begin{aligned}
&\left(2^n+1,2^k-1\right)\\
=&\left(\frac{2^{2n}-1}{2^n-1},2^k-1\right)\\
=&\frac{\left(2^{2n}-1,2^k-1\right)}{\left(2^n-1,2^k-1\right)}\\
=&\frac{2^{(2n,k)}-1}{2^{(n,k)}-1}
\end{aligned}
$$
我们分两种情况讨论：
### $\frac k{(n,k)}$ 为奇数
也就是说 $(k,2n)=(k,n)$，那么
$$
\begin{aligned} \left(2^{2n}-1,2^k-1\right)=\left(2^n-1,2^k-1\right)&=2^{(n,k)}-1\\
\left(2^n+1,2^k-1\right)&=1
\end{aligned}
$$
条件转化为
$$
\left(2^n+1\right)\mid t
$$
由于 $1\le t\le 2^n$，显然有 $B_k=0$。
### $\frac k{(n,k)}$ 为偶数
那么 $(k,2n)=2(k,n)$，则有
$$
\begin{aligned}
\left(2^{2n}-1,2^k-1\right)&=2^{2(n,k)}-1\\
\left(2^n-1,2^k-1\right)&=2^{(n,k)}-1\\
\left(2^n+1,2^k-1\right)&=2^{(n,k)}+1
\end{aligned}
$$
条件转化为
$$
\frac{2^n+1}{2^{(n,k)}+1}\mid t
$$
由于 $1\le t\le 2^n$，则 $B_k=2^{(n,k)}$。
---
总结一下
$$
B_k=
\begin{cases}
2^{(n,k)},&2\mid\frac k{(n,k)}\\
0,&\text{otherwise.}
\end{cases}
$$
记 $n=2^qp$（$p$ 为奇数），那么
$$
2\mid\frac k{(n,k)}\iff 2^{q+1}\mid k
$$
套用反演可得
$$
A_k=\sum_{d|k}\mu(d)B_{k/d}
$$
我们考虑到原题要求的 $P^0,P^1,P^2,\dots,P^{n-1}$ 的不动点个数之和似乎并不是非常的 canonical：最长的环有 $2n$ 长怎么只求前 $n$ 个？我们不妨先求出 $P^0,P^1,P^2,\dots,P^{2n-1}$ 的不动点个数之和，记之为 $g(n)$。
首先我们观察到环长必须得是 $(2n)$ 的约数。由于一个长度为 $w$ 的环对 $f(n)$ 的贡献为 $\left(\frac{2n}w\right)$，对 $g(n)$ 的贡献为
$$
\left\lfloor\frac nw\right\rfloor=\frac12\left(1+\frac{2n}w\right)
$$
于是就有 $f(n)=\frac12\left(g(n)+2^n\right)$。我们只需要求出 $g(n)$ 即可。
整理式子之前现有一个小定理：
> 定理三：
>
$$
\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor=1
$$
证明：
$$
\begin{aligned}
&\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor\\
=&\sum_{k=1}^n\mu(k)\sum_{k|d,d\le n}1\\
=&\sum_{d=1}^n\sum_{k|d}\mu(k)\\
=&\sum_{d=1}^n\left[d=1\right]\\
=&1
\end{aligned}
$$
于是开始整理式子：
$$
\begin{aligned}
g(n)&=\sum_{k=1}^{2n}\left\lfloor\frac{2n}k\right\rfloor\sum_{d|k}\mu(d)B_{k/d}\\
&=\sum_{k=1}^p\left\lfloor\frac pk\right\rfloor\sum_{d|2Qk}\mu(d)B_{2Qk/d}\\
&=\sum_{k=1}^p\left\lfloor\frac pk\right\rfloor\sum_{d|k}\mu\left(\frac kd\right)2^{Q(d,p)}\\
&=\sum_{g|p}2^{Qg}\sum_{k=1}^{\frac pg}\left\lfloor\frac p{kg}\right\rfloor\sum_{d|k}\mu\left(\frac kd\right)\sum_{t|d,t|\frac pg}\mu(t)\\
&=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\sum_{d=1}^{\frac p{gt}}\sum_{k=1}^{\left\lfloor\frac p{gtd}\right\rfloor}\left\lfloor\frac p{kgtd}\right\rfloor\mu(k)\\
&=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\sum_{d=1}^{\frac p{gt}}1\\
&=\sum_{g|p}2^{Qg}\sum_{t|\frac pg}\mu(t)\frac p{gt}\\
&=\sum_{g|p}2^{Qg}\phi\left(\frac pg\right)\\
&=\sum_{g|p}2^{n/g}\phi(g)\\
&=\sum_{g|n,g\text{ is odd}}2^{n/g}\phi(g)
\end{aligned}
$$
嗯，于是我们拿到了 45 分。
## Subtask 3
我们考虑求 $g(n)$ 的前缀和 $G(n)$，再随便操作下就能求到 $f(n)$ 的前缀和 $F(n)$ 了。
$$
\begin{aligned}
G(N)&=\sum_{n=1}^N\sum_{g|n,g\text{ is odd}}2^{n/g}\phi(g)\\
&=\sum_{d=1}2^d\sum_{g=1}^{\left\lfloor\frac Nd\right\rfloor}\left[g\text{ is odd}\right]\phi(g)
\end{aligned}
$$
我们记
$$
S(n)=\sum_{k=1}^n\left[k\text{ is odd}\right]\phi(k)
$$
那么 $G(N)=\sum_{d=1}2^dS\left(\left\lfloor\frac Nd\right\rfloor\right)$。预处理好 $10^6$ 之内的 $S(n)$，我们就可以愉快地计算啦～
## Subtask 4
我们来观察这个 $S(n)$。首先我们注意到
$$
\phi(2n)=
\begin{cases}
\phi(n),&n\text{ is odd}\\
2\phi(n),&\text{otherwise.}
\end{cases}
$$
那么我们设 $H(n)=\sum_{k=1}^n\phi(k)$，则有
$$
\begin{aligned}
S(n)&=\sum_{k=1}^n\left[k\text{ is odd}\right]\phi(k)\\
&=H(n)-\sum_{k=1}^n\left[k\text{ is even}\right]\phi(k)\\
&=H(n)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is even}\right]\phi(2k)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is odd}\right]\phi(2k)\\
&=H(n)-2\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is even}\right]\phi(k)-\sum_{k=1}^{\left\lfloor\frac n2\right\rfloor}\left[k\text{ is odd}\right]\phi(k)\\
&=H(n)-2\left(H\left(\left\lfloor\frac n2\right\rfloor\right)-S\left(\left\lfloor\frac n2\right\rfloor\right)\right)-S\left(\left\lfloor\frac n2\right\rfloor\right)\\
&=H(n)-2H\left(\left\lfloor\frac n2\right\rfloor\right)+S\left(\left\lfloor\frac n2\right\rfloor\right)\\
&=H(n)-2H\left(\left\lfloor\frac n2\right\rfloor\right)+H\left(\left\lfloor\frac n2\right\rfloor\right)-2H\left(\left\lfloor\frac n4\right\rfloor\right)+\cdots\\
&=H(n)-H\left(\left\lfloor\frac n2\right\rfloor\right)-H\left(\left\lfloor\frac n4\right\rfloor\right)-H\left(\left\lfloor\frac n8\right\rfloor\right)-\cdots
\end{aligned}
$$
那么用杜教筛计算 $H(n)$ 即可。这样的话，计算单个 $S(n)$ 会需要计算 $\log n$ 次 $H(n)$，加之我们需要算 $\sqrt N$ 个不同位置的 $S(n)$，看似时间复杂度爆表，实则不然。
记 $D(n)=\left\{n,\left\lfloor\frac n2\right\rfloor,\left\lfloor\frac n3\right\rfloor,\left\lfloor\frac n4\right\rfloor,\cdots\right\}$（不要给我以初中老师的口吻说集合不可重… 自动去重，啊，自动去重），那么我们知道杜教筛在计算 $H(n)$ 时实际上是对 $D(n)$ 中的所有数都计算了一遍 $H(n)$ 并存入了缓存。我们注意到，由于我们求的 $G(N)=\sum_{d=1}2^dS\left(\left\lfloor\frac Nd\right\rfloor\right)$，也就是说我们要求的 $S(x)$ 是满足 $x\in D(N)$ 的，而根据：
> 定理四：$\left\lfloor\frac{\left\lfloor\frac np\right\rfloor}q\right\rfloor=\left\lfloor\frac n{pq}\right\rfloor
我们知道我们在求 S(x) 时，需要求的 H(x),H\left(\left\lfloor\frac x2\right\rfloor\right),H\left(\left\lfloor\frac x3\right\rfloor\right),\dots 这些东西实际上也是在 D(N) 中，也就是被计算并缓存过的。因此总的时间复杂度依旧等同于做一次杜教筛的复杂度（当然是计算 H(n) 的部分，其它地方不一定，但不会影响总复杂度），也就是 O(N^{2/3})（如果预处理前 N^{2/3} 个 H(n) 的话）。
ametus.h / dream.cpp