数论比赛笔记

T1

$k=1$ 时候

$p_i = i$, $p_i \neq i, p_{p_i} = i$.

$f_n$ 表示 $n$ 的答案。

1. $p_1 = 1$, $f_{n - 1}$
2. $p_1 = i \neq 1$. $p_i = 1$. $(n-1)f_{n-2}$.

$$f_n = f_{n-1} + (n-1)f_{n-2}.$$

$O(n)$

$k$ 任意

$f_n$ 表示答案

从 $1$ 出发，走若干步回到 $1$，步数一定是 $2^k$ 的因数。

枚举这个因数。之后要知道中间路过了哪些点。

T2

$\gcd(n, m) = 1$

$b_j$ 可以对应到哪些 $a_i$:
$j \bmod n, (j + m) \bmod n, (j + 2m) \bmod n, \dots$

恰好可以遍历所有的 $i$ (按一定顺序）

无论从哪个 $j$ 开始，如果这一步匹配到了 $i$，下一步一定会匹配到 $(i + m) \bmod n$.

把 $a$ 重新排序：

$a_1, a_{1 + m}, a_{1 + 2m}, a_{1 + 3m}, \dots$.

$c_k = a_{1 + (k-1)m}$

$c$ 也以 $n$ 为周期。
如果 $j$ 第一步匹配到 $c_u$, 之后就会匹配到 $c_{u+1},c_{u+2},\dots$.
也就是若干个周期加上单个周期内的一个区间。

相当问：对每个 $j$, 对应的区间内有多少个 $c_i$ 比 $b_j$ 小。

离散化，扫描，树状数组维护区间和

$\gcd$ 不一定是 $1$

这时候设 $d = \gcd(n, m)$

可以发现只有在 $i \equiv j \pmod d$ 的时候他们两个才会匹配上。

所以我们按 ${}\bmod d$ 分组，每组分别做。就可以了。

T3

二分答案

之后只需要判断是否存在 k 条白色边的生成树。

只需要求出白色边最多/最少多少条。

性质：假设有一张图，有两个森林 $S, T$，如果 $S$ 的边数少于 $T$ 的边数，那么一定可以从 $T$ 里选出一条边加到 $S$ 里，还是森林。

T4

$(1, a^{\varphi(m)} \bmod m)$

记 $g_m(a)$ 表示有多少个 $n$ 使得 …

$g_m(a) = g_m(\gcd(a, m)).$

$a = dx, m = dy$

$a^n \bmod m = d^nx^n \bmod dy$
$=d\bigl(d^{n-1}x^n \bmod y\bigr)$

$x$ 和 $y$ 是互质的。所以说 $x \bmod y$ 满足欧拉定理。
并且因为互质

如果 $u, v$ 互质，$ux \equiv uy \pmod v$ 当且仅当 $x \equiv y \pmod v$.

也就是说 $g_m(a) = g_m(d)$.

进一步

$g_m(d)$ 怎么计算。

$u_k = \gcd(d^k, m)$.
$u_0 < u_1 < \dots < u_s = u_{s+1} = u_{s+2} = \dots$.

断言：$g_m(d) = s$。也就是说 $d^n \not\equiv d^{n + \varphi(m)}$ 当且仅当 $n < s$.

1. 如果 $n < s$. 那么 $\gcd(d^n, m) \neq \gcd(d^{n + \varphi(m)}, m)$. 那么 $(d, n)$ 肯定是合法的对。
2. 如果 $n \geqslant s$.
   我们要说明 $d^n \equiv d^{n + \varphi(m)}$.

$$\begin{aligned}
d^n &= u_s \frac{d^n}{u_s} \
d^n \bmod m &= u_s \left(\frac{d^n}{u_s}
\bmod \frac{m}{u_s}\right) .
\end{aligned}$$

$d$ 是和 $\frac{m}{u_s}$ 互质的。
所以说后面这个括号里的东西其实都是满足欧拉定理条件的。

因此我们设质因数分解

$$m = \prod_i p_i^{x_i}, d = \prod_i p_i^{y_i} \neq 1.$$

就可以得到

$$u_k = \gcd(d^k, m) = \prod_i p_i^{\min(x_i. ky_i)}$$

$$g_m(d) = s = \max\left(\bigl\lceil \frac{x_i}{y_i} \bigr\rceil \middle| y_i \neq 0\right)$$

使用 DP 计算答案。

对于一个 $m$, 设 $m = p^k l$, $p \nmid l$.

$f_{m,i}$ 表示有多少个 $a$ 使得 $g_m(a) = i$.

考虑：$a = p^v b, p \nmid b, g_l(b \bmod l) = j$.

这种情况下

$g_m(a) = s = \begin{cases}
j & v = 0, \
\max(\lceil k/v \rceil, j) & v > 0.
\end{cases}$

用 $f_{l, j}$ 转移 $f_{m, s}$.
转移的系数：给定 $b \bmod l$ 和 $v$，能选出多少个 $a$ 来。也就是 $\varphi(p^{k-v})$.

$[1, …, p^k l]$ 里面有多少个数 ${}\bmod (p^v l) = p^v (b \bmod l)$ 并且和 $v$ 互质.

取一个 m 的质因数 p
k = 0, l = m
while l % p == 0:
  l /= p
  k++

for v <= k
  for j
    s = v ? j : max(ceil(k / v), j));
    if v < k: f[m][s] += f[l][j] * phi(p^(k-v));
    else: f[m][s] += f[l][j] * p^(k-v);

复杂度计算：$q_m$ 表示 $m$ 的质因子次数的最大值。
那么复杂度不超过 $O(\sum q_m^2)$.

$O(\sum_m \sum x_i^2) = O(\sum_p \sum_k (2k+1) \frac{M}{p^k}) = O(M \sum_p \frac{1}{p^2})$

总复杂度是 $O(m)$.

$$\begin{aligned}
&\sum_{i = 1}^n \gcd(i, n)\
=&\sum_{i = 1}^n \sum_{d \mid \gcd(i, d)} \varphi(d)\
=&\sum_{d \mid n} \varphi(d) \frac{n}{d}.
\end{aligned}$$

$$ans(p^k) = kp^{k-1}(p-1)+p^k$$

$$2^{2^{2^\dots}} \bmod m$$

$$ans(m) = 2^{ans(\varphi(m)) + \varphi(m)} \bmod m.$$