数论分块

求 \(\sum f(i)g(\biggl\lfloor \dfrac{n}{i} \biggr\rfloor)\)，并且 \(f(i)\) 的前缀和可以快速计算。

发现 \(\biggl\lfloor \dfrac{n}{i} \biggr\rfloor\) 的取值只有根号种，暴力做就完事了。

问题是已知 \(l\)，怎么求出最大的 \(r\) 满足 \(\biggl\lfloor \dfrac{n}{l} \biggr\rfloor=\biggl\lfloor \dfrac{n}{r} \biggr\rfloor\) 呢？

推一推柿子，\(r=\biggl\lfloor\dfrac{n}{\biggl\lfloor\dfrac{n}{l}\biggr\rfloor}\biggr\rfloor\)。

做完了。

原根

本节的所有定义都是在模 \(p\) 意义下的。

如果 \(\gcd(a,p)=1\)，那么我们定义 \(a\) 的阶为最小的 \(l\) 满足 \(a^l \equiv 1 \pmod p\)，记为 \(\text{ord}_p a =l\)。

有一些性质：

\(\text{ord}_p a | \phi(p)\)。
\(a^l \equiv a^{l \bmod \text{ord}_p a} \pmod p\)。
若 \(a^l \equiv 1 \pmod p\)，则 \(l \equiv 0 \pmod {\text{ord}_p a}\)。

对于某个原根 \(g\)，它满足 \(\text{ord}_p g=\phi(p)\)。

于是可以得到，\(\forall b,\gcd(b,p)=1\)，\(b=g^x\)，又因为这个性质，所以我们只要找出最小原根 \(g\) 就能求出所有原根。

有结论：形如 \(2,4,p^k,2 \times p^k\)（\(p\) 为奇素数，\(k\) 为正整数）的数有原根。

如何求最小原根？

从小到大枚举，最小原根不会超过 \(n^{0.25}\)（不会证明）。

暴力 \(\rm check\) 是 \(\mathcal O(n)\) 的，设 \(\phi(n)=\prod p_i^{a_i}\)，我们可以只检验 \(\dfrac{\phi(n)}{p_i}\)。

杜教筛

求 \(\phi(i)\)，\(\phi(i) \times i\)，\(\phi(i) \times i^2\)，\(\mu(i)\) 等积性函数的前缀和。

假设我们要求函数 \(f\) 的前缀和，设 \(S(n)=\sum_{i=1}^n f(i)\)。那么我们需要寻找另一个积性函数 \(g\)，得到一个柿子：

\[g(1)S(n)=\sum_{i=1}^n (f*g)(i)-\sum_{i=2}^n g(i)S(\biggl\lfloor \dfrac{n}{i} \biggr\rfloor) \]

也就是说，如果我们能快速求出 \(f\) 和 \(g\) 的狄利克雷卷积前缀和以及 \(g\) 的前缀和，那么我们就能快速求出 \(f\) 的前缀和。

如果直接做是 \(\mathcal O(n^{\frac{3}{4}})\) 的，若能线性筛筛出前 \(n^{\frac{2}{3}}\) 个 \(f(i)\) 的话，可以优化到 \(\mathcal O(n^{\frac{2}{3}})\)。

杜教筛的关键在于那个柿子以及 \(g\) 的选取。

离散对数

给定一个质数 \(p\)，以及一个整数 \(b\)，一个整数 \(n\)，现在要求你计算一个最小的非负整数 \(l\)，满足 \(b^l \equiv n \pmod p\)。

由于 \(b,p\) 互质，\(b\) 有逆元，所以可以在模意义下乘除 \(b\)。

首先有 \(l=xB-y\)，\(b^{xB-y} \equiv n \pmod p\)，然后 \(b^{xB} \equiv nb^y \pmod p\)。

取 \(B=\sqrt p\)，那么前面的 \(b^{xB}\) 可以暴力跳，后面的 \(nb^y\) 可以暴力预处理。

做完了，时间复杂度 \(\mathcal O(\sqrt p)\)。

求 \(x^A \equiv B \pmod {2k+1}\)，\(x \in [0,2k]\) 的 \(x\) 的个数，要求根号复杂度。

首先由于 \({2k+1}\) 并不是质数，很难做。

发现 \({2k+1}=\prod {p_i^{a_i}},p_i \in \text{Prime}\)，我们可以解出所有 \(x^A \equiv B \pmod {p_i^{a_i}}\) 方程，然后原方程解的个数就是这些方程的解的个数的乘积（由 \(\rm CRT\) 可知）。

考虑一个 \(x^A \equiv B \pmod {p_i^{a_i}}\) 怎么解，设 \(d\) 为最小解，不难发现方程的解一定是 \(x_i=kd\) 的形式（一个数满足条件它的倍数一定满足）。

然后先分类讨论一下：

\(B \equiv 0 \pmod {p_i^{a_i}}\)，此时 \(B=p_i^b\)，设 \(d=p_i^{s}\)，那么显然有 \(As \ge a_i\)，所以 \(s\) 的最小值就是 \(\biggl\lceil \dfrac{a_i}{A} \biggr\rceil\)，那么 \(d=p_i^{s}\)，解的个数为 \(\frac{{p_i^{a_i}}}{d}=p_i^{a_i-s}\)。
\(B \not \equiv 0 \pmod {p_i^{a_i}}\)，此时 \(B=p_i^{b} \times q\)，显然如果 \(b\) 不是 \(A\) 倍数无解，那么设 \(b=k \times A\)，所以得到 \((p_i^k \times y)^A \equiv p_i^{b} \times q \pmod {p_i^{a_i}}\)，也就是 \(p_i^b \times y^A \equiv p_i^{b} \times q\pmod {p_i^{a_i}}\)。

然后就可以等式两边同除 \(p_i^b\)（吗）？

如果上述成立，那么 \(p_i^b \times y^A \equiv p_i^b \times q \pmod {p_i^{a_i}}\) 的解的个数等价于 \(y^A \equiv q \pmod {p_i^{a_i-b}}\) 的解的个数，但是我们发现出问题了，原方程的解的个数应该是放缩后方程的解的个数的 \(p_i^{b-k}\) 倍，因为原来 \(y\) 的范围是 \([0,p_i^{a_i-k})\)，但是后面变成了 \([0,p_i^{a_i-b})\)，范围缩小到原来的 \(p_i^{b-k}\)，解数自然也缩小到原方程的 \(p_i^{b-k}\)。

问题转化为求方程 \(y^A \equiv q \pmod {p_i^{a_i}}\) 的解的个数，显然 \(\gcd(p_i,q)=1\)，设 \(p_i\) 的原根为 \(g\)，那么有 \(p_i=g^{kp}\)，\(y=g^{ky}\)。

\(kp\) 和 \(ky\) 可以 \(\rm BSGS\) 直接来。

然后就变成了 \(g^{ky \times A} \equiv g^{kp} \pmod {p_i^{a_i}}\)，然后有 \(ky \times A \equiv kp \pmod {\phi({p_i^{a_i}})}\)。

此时只要求出这个同余方程的解数即可，不难发现该方程的解与原方程的解一一对应。

而这个同余方程若有解，解数必然为 \(\gcd(\phi({p_i^{a_i}}),A)\)。