T1#

时候#

, .

表示的答案。

,
. . .

任意#

表示答案

从出发，走若干步回到，步数一定是的因数。

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

T2#

可以对应到哪些 :

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

无论从哪个开始，如果这一步匹配到了，下一步一定会匹配到 .

把重新排序：

也以为周期。如果第一步匹配到 , 之后就会匹配到 . 也就是若干个周期加上单个周期内的一个区间。

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

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

不一定是 #

这时候设

可以发现只有在的时候他们两个才会匹配上。

所以我们按分组，每组分别做。就可以了。

T3#

二分答案

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

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

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

T4#

记表示有多少个使得 …

和是互质的。所以说满足欧拉定理。并且因为互质

如果互质，当且仅当 .

也就是说 .

进一步#

怎么计算。

. .

断言：。也就是说当且仅当 .

如果 . 那么 . 那么肯定是合法的对。
如果 . 我们要说明 .

Misplaced &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.$$

数论比赛笔记

T1#

时候#

任意#

T2#

不一定是 #

T3#

T4#

进一步#

Comments