理论基础
中国剩余定理及拓展
已知 \(x \equiv a_i (\bmod p_i\ )\)，求 \(x \bmod \operatorname{lcm}\{p_i\}\) 的值。
-
若 \(p_i\) 互质，那么我们只需要计算 \(c_i\) 使得
\[\prod\limits_{j \ne i} \cdot c_i \bmod p_i = 1 \]然后有
\[x = \sum\limits_{i}c_ia_i\prod\limits_{j\ne i}p_j \bmod (\prod p_i) \] -
若 \(p_i\) 不互质，我们考虑如何合并两个方程。设
\[x = p_1c_1 + a_1 = p_2c_2 + a_2 \]则有
\[p_1c_1-p_2c_2=a_2-a_2 \]可以直接 \(\text{exgcd}\) 求出一组可行的 \(c_1, c_2\)，就能得到 \(x \bmod \operatorname{lcm}(p_1, p_2)\)。
Miller-Rabin 算法
费马小定理：如果 \(p\) 是素数，则 \(\forall 1 \le x < p, x^{p-1} \equiv 1 (\bmod p\ )\)。
考虑逆否定理，如果存在一些 \(x\) 使得 \(x^{p-1} \not\equiv 1(\bmod p\ )\) 则 \(p\) 一定不是质数。于是我们随机一些 \(x\) 来判定。
二次探测定理：在 \(p\) 是质数的情况下，如果 \(x^2 \equiv 1 (\bmod p\ )\)，那么 \(x \equiv 1(\bmod p\ )\) 或 \(x \equiv p-1(\bmod p\ )\)。
于是我们将 \(p\) 分解为 \(q \cdot 2^k + 1\) 后可以先算出 \(y = x^q\)，然后每次 \(y \leftarrow y^2\)，用二次探测定理判定。
如果我们随机 \(c\) 个 \(x\)，正确率为 \(1 - 4^{-c}\)。
Pollard-Rho 算法
假设 \(a\) 是合数，如何将它分解为 \(x \times y\) 的形式，其中 \(x, y > 1\)。
设 \(f(x) = (x^2 + c) \bmod a\) ，其中 \(c\) 是随机选的一个常数，然后我们可以进行以下过程：
- 随意指定初始值 \(x, y\)，其中 \(x = y\) 。
- 每次 \(x \leftarrow f(x), y \leftarrow f(f(y))\) 直到操作后 \(\gcd(x - y, a) \ne 1\) 或者 \(x = y\) 为止。
- 如果是前者，则分解成功了，否则分解失败，重新选择 \(c, x\) 开始。
这个套圈的过程我们可以通过倍增把算 \(\gcd\) 的 \(\log\) 优化掉。
如果认为 \(f\) 是一个随机映射，则根据生日悖论，期望时间复杂度为 \(\mathcal O(\sqrt{p})\) 即 \(\mathcal O(n^{\frac14})\) 。
Lucas 定理
对于素数 \(p\) ，有
\[\binom{n}{m} = \binom{\lfloor\frac np\rfloor}{\lfloor\frac mp\rfloor} \binom{n \bmod p}{m \bmod p} (\bmod p\ ) \]
证明考虑 \((1+x)^p = 1 + x^p\) 。可以写出阶乘因子后先数出 \(p\) 的因子个数，然后对于 \(p\) 的倍数，非 \(p\) 的倍数部分分开计算。
拓展 Lucas 定理
对于 \(p\) 不是素数的情况，首先可以拆成质数幂然后 CRT 合并。
对于质数幂的情况，我们可以先计算 \(p\) 的指数，然后用类似的方法计算去掉所有 \(p\) 因子之后 \(n! \bmod p^k\) 的值。
欧拉筛
线性求 \(f(1), f(2), \ldots, f(n)\) 。其中 \(f\) 是积性函数，且可以在 \(\mathcal O(1)\) 时间内计算 \(f(p^k)\)。
杜教筛
求 \(\sum\limits_{i \le n} f(i)\) 。我们可以找到 \(g, s\) 使得 \(g * f = s\) 且 \(g, s\) 前缀和都容易计算，同时 \(g(1) = 1\) 。
令 \(F, G, S\) 分别是 $f, g,s $ 的前缀和，则
\[\begin{aligned} S(n) &=\sum_{d | n} f(d)g(\dfrac nd)\\ F(n) &= \sum_{i=1}^n(s(i) - \sum_{j|i,j\ne i}f(j)g(\dfrac ij))\\ &= S(n) - \sum_{k=2}^n\sum_{j=1}^{n//k}g(k)f(j)\\ &= S(n) - \sum_{k=2}^n g(k)F(n//k) \end{aligned} \]可以对其进行整除分块然后递归，存进一个哈希表，直接这样算时间复杂度 \(\mathcal O(n^{\frac34})\)，预处理前 \(\mathcal O(n^\frac23)\) 复杂度就是 \(\mathcal O(n^\frac23)\) 了。
求所有 \(f(\lfloor\frac ni\rfloor)\)：
\[\begin{cases} f_1(i) = f(i)&\ i \le \sqrt n\\ f_2(i) = f(\lfloor\frac ni\rfloor) &\ i > \sqrt n \end{cases} \]Powerful Number 筛
定义 Powerful Number 为所有满足所有质因子指数都 \(> 1\) 的数，可以证明这样的数不超过 $\mathcal O(\sqrt n) $ 个，且一定可以表示为 \(a^2b^3\)、
假设我们能构造出一个积性函数 \(g\) 使得 \(g(p) = f(p)\)，且 \(g\) 的前缀和易求，令 \(h\) 满足 \(h * g = f\) ，则有 \(h\) 只在 Powerful Number 处不为 \(0\)。从而有：
\[\begin{aligned} F(n) &= \sum_{i=1}^nf(i)\\ &= \sum_{i=1}^n\sum_{j|i}h(j)g(\dfrac ij)\\ &= \sum_{i=1}^n h(j)G(\lfloor\dfrac nj \rfloor) \end{aligned} \]于是我们枚举 Powerful Number 然后计算即可。
Min_25 筛
要求：\(f(p)\) 是一个关于 \(p\) 项数较少的多项式，\(f(p^c)\) 可以快速计算。
我们考虑记一个 \(F(n, k)\) 表示 \(n\) 以内最小质因子 \(\ge k\) 的数 \(x\) 的 \(f(x)\) 和，记 \(G(n)\) 为 \(n\) 以内质数位置 \(f(x)\) 和，则：
\[\begin{aligned} F(n, k)=\sum_{i=2}^n \end{aligned} \]假设我们求出了 \(G\)，计算 \(F\) 的时候对于只有一个质因子的可以用 \(g\) 算，否则我们枚举最小的质因子和它的次数，然后递归下去计算。
这部分直接递归的时间复杂度是 \(\mathcal O(n^{1-\varepsilon})\)，常数较小。
然后考虑怎么计算 \(g(n)\)。现在我们暂时认为 \(f(p) = p^c\)，令 \(g(x) = x^c\) ，则 \(g\) 为完全积性函数。
因此我们可以用一个类似埃氏筛的过程，\(G(n, k)\) 为筛完前 \(k\) 个素数后剩下位置（包含质数位和最小质因子 \(> k\) 的位置）\(g\) 的和。这部分时间复杂度也是 \(\mathcal O(\frac{n^\frac34}{\log n})\)。
类欧几里得算法
计算
\[f(a, b, c, n) = \sum_{i = 0}^n \left\lfloor\dfrac{ai+b}{c}\right\rfloor \]
先认为 \(0 \le a, b < c\)，否则可以简单转化成这种形式，否则（记 \(m = \left\lfloor\dfrac{an+b}{c}\right\rfloor\)）：
\[\begin{aligned} f(a, b, c, n) &= \sum_{i=0}^n\sum_{j=1}^m [j \le \dfrac{ai+b}c]\\ &= \sum_{i=0}^n\sum_{j=0}^{m-1} [i > \dfrac{jc + c - b - 1}a]\\ &= nm - \sum_{j=0}^{m-1} [i > \dfrac{jc + c - b - 1}a]\\ &= nm - f(c, c - b - 1, a, m - 1) \end{aligned} \]最终的 \(c\) 可以取模（即上文「转化」）：
\[f(a, b, c, n) = f(a \bmod c, b \bmod c, c, n) + \dfrac{n(n+1)}2\left\lfloor\dfrac ac\right\rfloor + (n+1)\left\lfloor\dfrac bc\right\rfloor \]计算
\[\begin{aligned} g(a, b, c, n) &= \sum_{i=0}^n i\left\lfloor\dfrac{ai+b}{c}\right\rfloor\\ h(a, b, c, n) &= \sum_{i=0}^n \left\lfloor\dfrac{ai+b}{c}\right\rfloor^2 \end{aligned} \]
首先演绎 \(g\)。
先取模：
\[g(a, b, c, n) = g(a \bmod c, b \bmod c, c, n) + \dfrac{n(n+1)(2n+1)}6\left\lfloor\dfrac ac\right\rfloor + \dfrac{n(n+1)}2\left\lfloor\dfrac bc\right\rfloor \]那么：
\[\begin{aligned} g(a, b, c, n) &= \sum_{j = 0}^{m-1}\sum_{i=0}^n i \cdot [j < \left\lfloor\dfrac{ai+b}{c}\right\rfloor] \end{aligned} \]记 \(t = \left\lfloor\dfrac{jc + c - b - 1}{a}\right\rfloor\)，则可以得到
\[\begin{aligned} g(a, b, c, n) &= \sum_{j = 0}^{m-1}\sum_{i=0}^n i \cdot [i > t]\\ &= \sum_{j=0}^{m-1}\dfrac 12 (t + n - 1)(n - t)\\ &= \dfrac 12 \left[mn(n + 1) - \sum_{j=0}^{m-1} t^2 - \sum_{j=0}^{m-1}t \right]\\ &= \dfrac12 [mn(n+1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1)] \end{aligned} \]然后演绎 \(h\)。
先取模：
\[\begin{aligned} h(a, b, c, n) &= h(a \bmod c, b \bmod c, c, n)\\ &+ 2\left\lfloor\dfrac bc\right\rfloor f(a \bmod c, b \bmod c, c, n) + 2\left\lfloor\dfrac ac\right\rfloor g(a \bmod c, b \bmod c, c, n)\\ &+\dfrac{n(n+1)(2n+1)}6\left\lfloor\dfrac ac\right\rfloor^2 + (n+1)\left\lfloor\dfrac bc\right\rfloor^2 + n(n+1)\left\lfloor\dfrac ac\right\rfloor\left\lfloor\dfrac bc\right\rfloor \end{aligned} \]以下沿用 \(m, t\)。
我们发现平方不好处理，于是考虑如下拆分：
\[n^2 = 2\dfrac{n(n+1)}2 - n = \left(2\sum_{i=0}^ni\right) - n \]这样添加变量 \(j\) 时只会出现一个求和算子，而不会出现 \(\sum \times \sum\) 的情况。
于是
\[\begin{aligned} h(a, b, c, n) &= \sum_{i=0}^n \left\lfloor\dfrac{ai+b}{c}\right\rfloor^2\\ &= \sum_{i = 0}^n \left[\left(2\sum_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j\right) - \left\lfloor\dfrac{ai+b}{c}\right\rfloor\right]\\ &= \left(2\sum_{i=0}^n \sum_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j \right) - f(a, b, c, n)\\ \sum_{i=0}^n \sum_{j=1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor}j &= \sum_{i = 0}^n \sum_{j = 1}^{\left\lfloor\frac{ai+b}{c}\right\rfloor - 1} (j + 1)\\ &= \sum_{j= 0}^{m - 1}(j + 1) \cdot \sum_{i = 0}^n \left[j < \left\lfloor\dfrac{ai+b}{c}\right\rfloor \right]\\ &= \sum_{j= 0}^{m - 1}(j + 1) \cdot \sum_{i = 0}^n [i > t]\\ &= \sum_{j= 0}^{m - 1}(j + 1)(n-t)\\ &= \dfrac 12 nm(m + 1) - \sum_{j= 0}^{m - 1}(j + 1)t\\ &= \dfrac 12 nm(m + 1) - g(c, c-b-1, a, m - 1) - f(c, c-b-1, a, m - 1) \end{aligned} \]因此化简可得
\[\begin{aligned} f(a, b, c, n) &= nm - f(c, c - b - 1, a, m - 1)\\ g(a, b, c, n) &= \dfrac12 [mn(n+1) - h(c, c - b - 1, a, m - 1) - f(c, c - b - 1, a, m - 1)]\\ h(a, b, c, n) &= nm^2 - 2g(c, c-b-1, a, m - 1) - f(c, c-b-1, a, m - 1) \end{aligned} \]在计算时可以考虑三个一起同步计算。时间复杂度 \(\mathcal O(\log n)\)。
例题
ISIJ2019T1
给定 \(n, m\)，求有多少长度为 \(n\) 的序列 \(\{a\}\) 满足 \(1 \le a_i \le m\) 且 \(a_i < \min \{a_{i+2}, a_{i + 3} \}\)。对 \(1000003\) 取模。
原题 \(n, m \le 1000\)，加强版 \(n, m \le 10^{18}\)。
考虑把满足条件的序列划分成极长不上升子段。显然每段长度 \(\le 2\)，并且第 \(i\) 段的 $\max < $ 第 \(i + 1\) 段的 \(\min\)。
第一条显然，第二条的证明如下：
- 如果以 \(i\) 开头的段长度为 \(2\)，那么由 \(a_i < a_{i + 2}, a_{i + 3}\) 得证。
- 如果以 \(i\) 开头的段长度为 \(1\)，那么考虑以 \(i + 1\) 开头的段长度，如果为 \(1\)，那么根据「极长不上升子段」得 \(a_i < a_{i + 1}\)，否则由 \(a_i < a_{i + 2}\) 得证。
类似地可以反过来证明每一个满足划分后条件的序列都满足要求。
所以变成统计划分后的段。枚举有多少段长度为 \(2\)，把这些段的两个数交换顺序就会变成一个不降序列，其中如果在一个段内则可以相等。直接组合数统计即可。
\(10^{18}\) 小模数的情况，可以使用 Lucas 定理，拆成每一位乘积，然后数位 DP。
AGC003D Anticube
有 \(n\) 个数，你需要选出尽量多的数，使得任意两个的乘积都不是完全立方数。
\(n \le 10^5, a_i \le 10^{10}\)。
首先想到分解质因数。但是显然不可暴力分解。于是先咕掉这个环节。
在分解后，我们注意到题目只关心质因数的幂次对 \(3\) 取模后的结果。于是我们对所有的 \(p^k\) 的 \(k \leftarrow k \bmod 3\)，这样有一些数会变得相等，我们将它们放到同一类中，用这个相同的结果代表这一类。
这时，对于一个处理后的代表 \(x\)，我们都能够找一个最小的 \(y\) 使得 \(xy\) 为完全立方数。这样的 \(y\) 显然是唯一的。因此我们存在若干对这样的矛盾关系。在每一对矛盾关系中，我们选择类大小较大的加入答案即可。
回到质因数分解。我们可以先预处理出 \(10^5\) 内的每一个素数及其平方。然后对于每一个数，我们暴力用 \([2, \sqrt[3]x]\) 内的素数试除，暴力计算指数\(\bmod 3\) 的值。操作后，结果仅可能有：
- 最后剩下的数为 \(1\)。
- 最后剩下的数为 \(\prod p_i\)。
- 最后剩下的数为 \(p_k^2\)。
\(2, 3\) 是好区分的。因此对于情况 \(2, 3\)，我们已经有足够的信息继续算法。
时间复杂度 \(\mathcal O(n\sqrt[3]V)\)。
LOJ6714 Stupid Product
定义一个长度为 \(m\) 的正整数序列 \(\{a\}(\forall i \in [1, m], a_i > 1)\) 的权值为 \(\prod a_i\)。特别地，空序列的权值为 \(1\)。记权值为 \(x\) 的序列个数为 \(f(x)\)。
给定正整数 \(n\)，求 \(\left(\sum\limits_{i=1}^n f(i)\right) \bmod 998244353\)。
\(n \le 10^{10}\)。
不难发现
\[f(x)= \begin{cases} 1 &\ x=1\\ \sum_{d | x, d \ne x} f(d) &\ x > 1 \end{cases} \]因此要求
\[\begin{aligned} F(n) &= 1+\sum_{i=1}^n\sum_{j|i, j \ne i}f(j)\\ &= 1+\sum_{i=1}^n\left((\sum_{j|i}f(j)) - f(i)\right)\\ \Rightarrow 2F(n)-1 &=\sum_{i=1}^n\sum_{j|i}f(j)\\ &= \sum_{d=1}^n\sum_{i=1}^{\left\lfloor\tfrac nd\right\rfloor}f(i)\\ &= \sum_{d = 1}^nF(\left\lfloor\dfrac nd\right\rfloor)\\ \\ \Rightarrow F(n) &= 1+\sum_{d = 2}^nF(\left\lfloor\dfrac nd\right\rfloor) \end{aligned} \]杜教筛即可。
CF364D Ghd
定义 \(n\) 个数的「最大半公约数」为最大的 \(d\) 满足其为至少 \(\left\lceil\dfrac n2\right\rceil\) 个数的约数。
给定 \(n\) 个数，求他们的「最大半公约数」。
\(n \le 10^6, a_i \le 10^{12}\)。
随机化。每次从输入的 \(n\) 个数中随机选取一个记为 \(x\)，然后对 \(x\) 质因数分解，记录其所有正因子。记 \(cnt_i\) 表示 \(\{a\}\) 中有多少个数可以被 \(x\) 的第 \(i\) 个因数 \(d_i\) 整除，则我们从大到小枚举 \(d_i\)，如果 \(cnt_i \ge \left\lceil\dfrac n2\right\rceil\)，则 \(d_i\) 就是我们想要的答案。
接下来思考如何求取 \(cnt_i\)。我们将 \(n\) 个数枚举一遍，每次找到 \(\gcd(x, a_i)\) 在 \(d\) 数组中的位置 \(\text{pos}\)，然后使 \(cnt_{\text{pos}} \leftarrow cnt_{\text{pos}} + 1\)。
同时，如果 \(d_i \mid d_j\)，那么 \(cnt_i \leftarrow cnt_i + cnt_j\)。这是因为我们仅对 \(\gcd\) 进行了记录，而没有记录其倍数。
对于整个操作，最终答案有 \(\dfrac 12\) 的概率是正确的。因此随机十次，大概可以通过本题。
CF571E Geometric Progressions
有 \(n\) 个等比数列 \(\{a_i, a_ib_i, a_ib_i^2, \ldots\}\)，求最小的在所有的等比数列中都出现的数 \(\bmod (10^9 + 7)\) 后的值，或宣告不存在。
\(n \le 100, a_i, b_i \le 10^9\)。
首先将 \(a_i, b_i\) 全部分解质因数，设 \(a_i = \prod_j p_j^{c_{i, j}}, b_i = \prod_j p_j^{d_{i, j}}\)。
对于某个 \(j\)，如果存在 \(d_{i, j} = 0\)，如果全 \(0\) 我们可以判断 \(c\) 是否相等，如果相等忽略，否则无解。
如果有 \(0\) 有非 \(0\)，易知最多一个可行解，找出来判断即可。
现在所有的 \(d_{i, j}\) 都不为 \(0\)。
我们对于两个不同的质因子 \(1, j\)，如果存在 \(i\) 使得 \(\dfrac{d_{1, j}}{d_{i, j}} \ne \dfrac{d_{1, 1}}{d_{i, 1}}\)，也最多一个可行解。
如果有 \(i\) 满足 \(d\) 成比例，可以判断一下 \(c\) 是否成比例，否则无解。
剩下就是一个 \(\text{exCRT}\) 了。
SPOJ20174 DIVCNT3 - Counting Divisors (cube)
定义 \(d(n)\) 为 \(n\) 的约数个数，求
\[S_3(n) = \sum_{i = 1}^n d(i^3) \]多组数据，\(T \le 10^4, n \le 10^{11}\)。时限 \(\text{20s}\)，空间限制 \(\text{1.46GB}\)。
考虑 Powerful Number。注意到 \(f(p) = d(p ^3) = 4\)，我们可以令 \(g(p) = d * d\)。
问题变为如何计算 \(G(n)\)。
\[\begin{aligned} G(n) &= \sum_{i \le n} (d * d)(i)\\ &= \sum_{ij \le n} d(i)d(j)\\ &= \sum_{i}d(i)\cdot\left(\sum_{i, j \le n} d(j)\right) \end{aligned} \]CF1552H Guess the Perimeter
平面中有个矩形满足四个顶点的横、纵坐标均在 \([1, 200]\) 之间，每次可以给任意个整点点求有多少个在矩形内，你需要在 \(4\) 次询问中求出它的周长。
先用一次询问查出面积。
考虑隔一行查一行，这样如果高是奇数就可以得到答案。
否则考虑每 \(4\) 行查一行，如果高\(\bmod 4 = 2\) 可以得到答案。
以此类推，注意到 \(2^8 > 200\)，就只有 \(7\) 种这样的查法，二分即可。
UOJ216 Jakarta Skyscrapers
有一个长度为 \(10^{18}\) 的 \(01\) 串 \(s\)，初始时全为 \(0\)。一开始给定 \(a, b\) ，令 \(s_a = s_b = 1\)。
定义一次操作为：对于某个 \(i, j\) 满足 \(s_i = s_j = 1\)，将 \(s_{i - j}\) 改为 \(1\)。
求能否在 \(400\) 次操作内将 \(s_c\) 改为 \(1\)。
\(1 \le a, b, c \le 10^{18}\)。
不考虑次数限制，能生成的数一定是 \(\gcd\) 的倍数，且不超过 \(\max(a,b)\)。
加入次数限制，考虑把 \((a,b)\leftarrow (a \bmod b,b)\) 倍增优化，即：
\[a\rightarrow a-b\rightarrow a-2b\rightarrow 2b\rightarrow a-4b\rightarrow 4b\rightarrow a-8b \]这样操作次数显然是 \(\mathcal O(\log n)\) 的。
CF1091G New Year and the Factorisation Collaboration
给一个大数 \(n\)，对其质因数分解。
提供高精度交互库，可以计算 \(x + y, x - y, x \times y, \dfrac xy, x^y, \sqrt x\) 在\(\bmod n\) 意义下的值。
一共可以使用不超过 \(100\) 次，同时除法和乘方时间需要不超过 \(\text{350ms}\)，开平方不超过 \(\text{80ms}\)。时限 \(\text{6s}\)。
保证 \(n\) 所有质因子不同，且个数在 \([2, 10]\) 之间，全部形如 \(4x + 3\) 的形式。
\(n \le 2^{1024}\)。
注意到它提供的库中只有 \(\sqrt{x}\) 我们难以计算。
考虑我们现在随机 \(x\)，询问 \(x' = \sqrt{y = x^2}\)，如果 \(x \ne x'\) 则 \((x - x')(x + x') \equiv 0\ (\bmod n\ )\)。
假设 \(n = \prod p_i\)，我们知道有 \(x' \equiv \pm x\ (\bmod p_i\ )\)。由于 \(x\) 随机，正负概率均为 \(\dfrac 12\) 。
也就是说，\(x - x'\) 和 \(x + x'\) 随机划分了 \(p_i\)。
多随机几次可以较稳定地求解。
校门外的树
给定一个序列，\(Q\) 次询问，每次给定一个区间 \(l, r\)，求
\[\left[\prod_{l \le i < j \le r} \gcd(a_i, a_j)\right] \bmod 998244353 \]\(n, Q, \max\{a_i\} \le 10^5\)。
先考虑如何计算答案：把每个数字 \(k\) 拆成 \(\prod p_i^{k_i}\) 的形式，其中 \(p_i\) 是第 \(i\) 个质数。
注意到
\[\gcd(a, b) = \prod p_i^{\min(a_i, b_i)} = \prod_i \prod_{j=1}^{\min(a_i, b_i)}p_i \]所以对于所有 \(p_i^j (j > 0)\) 如果同时是 \(a, b\) 的因数就会给答案产生 \(p_i\) 贡献。那么答案就是
\[\prod_{i, j} p_i^{\binom{c[p_i^j]}2} \]其中 \(c[x](c_x)\) 表示 \(x\) 的个数。
CF1030G Linear Congruential Generator
有 \(n\) 个线性同余生成器，每个形如 \(f_0, a, b, p\)，使得 \(f_i = (af_{i - 1} + b) \bmod p\)。
现在 \(p\) 给定，求对于所有的 \(f_0, a, b\)，能生成出的不同的 \([f_{1, i}, f_{2, i}, \ldots, f_{n, i}]\) 这样的 tuple 个数的最大值。
\(n \le 2 \times 10^5, p \le 2 \times 10^6, p \in \mathbb{P}\)。
注意到每个生成器都形如一个 \(\rho\)，也就是一个长度为 \(c\) 的环加上一个长度为 \(l\) 的柄，则答案为 \(\max l + \operatorname{lcm} c\)。
当 \(a = 0\) 则 \(l = 1, c = 1\)，当 \(a = 1\) 则 \(l = 0, c \mid p\) 。
否则由于 \(p\) 是质数，\((ax + b) \bmod p\) 可逆，因此 \(l = 0\)，然后有 \((a^c)x + b\sum\limits_{i = 0}^{l - 1}a_i \equiv x\ (\bmod p\ )\) ，即 \((a^c - 1)(x - \dfrac{b}{a-1}) \equiv 0\)，从而有 \(c \mid (p - 1)\)。
由于 \(l \le 1\)，所以我们用 \(\operatorname{lcm}\) 换 \(l\) 一定不优。从大到小对 \(p\) 贪心即可。
UOJ221 [NOI2016] 循环之美
求能用 \(\dfrac xy(1 \le x \le n, 1 \le y \le m)\) 表示的 \(k\) 进制纯循环小数个数。
\(n, m \le 10^9, k \le 2000\)。
题意相当于 \(\sum\limits_{1\leq x\leq n,1\leq y\leq m}[\gcd(x,y)=1][\gcd(y,k)=1]1\)。考虑反演。
\[\begin{align} &\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}=x\cdot\frac{y}{\gcd(x,y)}\\ &\sum_{1\leq x\leq n,1\leq y\leq m}[\gcd(x,y)=1][\gcd(y,k)=1]1\\ =&\sum_{1\leq x\leq n,y|k}\mu(x)\mu(y)\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{\mathrm{lcm}(x,y)}\rfloor\\ =&\sum_{1\leq x\leq n,y|k}\mu(x)\mu(y)\lfloor\frac{n}{x}\rfloor\lfloor\frac{\lfloor\frac{m}{x}\rfloor}{\frac{y}{\gcd(x,y)}}\rfloor\\ \end{align} \]可以发现 \(x\) 确定的时候，\(\mu(x),\lfloor\frac{n}{x}\rfloor,\lfloor\frac{m}{x}\rfloor\) 都是确定的，由于 \(y \mid k\)，\(\dfrac{y}{\gcd(x,y)}\) 和 \(\gcd(x, k), y\) 相关而不和 \(x\) 相关。
对 \(\lfloor\frac{n}{x}\rfloor,\lfloor\frac{m}{x}\rfloor\) 整除分块，则我们需要计算 \(\sum\limits_{l\leq x\leq r}[\gcd(x,k)=y]\mu(x)\)。
设
\[g(n,k,y)=\sum_{1\leq x\leq n}[\gcd(x,k)=y]\mu(x)\\ f(n,k)=g(n,k,1)\\ g(n,k,y)=\mu(y)f(\lfloor\frac{n}{y}\rfloor,k)\\ f(n,k)=\sum_{x=1}^n\mu(x)-\sum_{i|k,i\not=1}g(n,k,i) \]第二条正确性显然。
对于第一条，\(g(n,k,y)=\mu(y)f(\lfloor{\frac{n}{y}}\rfloor,\frac{k}{y})\)。有可能的区别是 \(k\) 某一种质因子，全部出现在 \(y\) 中。如果有 \(\ge 2\) 个，那么已经 \(\mu(y) = 0\) 了。如果只有 \(1\) 个，那么再来一个质因子就直接 \(=0\) 了，如果是 \(\dfrac ky\) 就不会 \(=0\) 所以合理。
\(\mu\) 前缀和可以用杜教筛，\(f\) 可以直接暴力，复杂度 \(\mathcal O(\sqrt n \cdot d(k))\)，预处理 \(\le n^{\tfrac 23}\) 的 \(f\) 就是 \(\mathcal O(\sqrt[3]n \cdot d(k) + n^{\tfrac 23})\)。
然后 \(y\) 的部分，可以预处理每个 \(x \mid k, \mu(x) \ne 0, y \mid k\) 时的 \(\dfrac{y}{\gcd(x, y)}\) 。
标签：lfloor,le,数论,dfrac,sum,笔记,20230801,rfloor,left From： https://www.cnblogs.com/alphayeung/p/17598966.html