20230801 数论基础学习笔记-526互联

理论基础

中国剩余定理及拓展

已知 $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$。

see NOI2016 循环之美 - lk's blog

题意相当于 $\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)}$ 。