初等数论学习笔记

· · 算法·理论

据说开头骗赞可以骗赞，那就骗赞吧。

目前未完成项目：

  1. BSGS

感觉这个东西根本更不完啊。

欢迎评论新内容。

差不多完工了。

排版有些糟糕，自己凑合着看吧（

先拿出一句巨佬 5k 说的话：

一些基本符号：

质数：

威尔逊定理：p 为质数的充要条件为 (p-1)!\equiv -1\pmod p。

证明：

反证，假设 $p$ 是合数。 如果 $p$ 为质数的平方，例如 $p=4$，则 $3!\equiv 2\pmod 4$，不成立。 令 $p=k^2$，因为 $p>4$，所以 $k>2,2k<p,(p-1)!\equiv 0\pmod p

否则存在 p=ab,a\not = b，则 (p-1)!\equiv nab\equiv 0\pmod p,n\in \mathbb{N}^+

若 $p$ 是素数，令集合 $A=\{1,2,3,\cdots.p -1\}$。 则 $A$ 构成模 $p$ 乘法的简化剩余系，即任意 $i\in A$，均存在 $j\in A$，使得 $ij \equiv 1 \pmod p$。 但是 $A$ 中的元素是不一定两两配对，需要考虑这种情况： $$x^2 \equiv 1\pmod p$$ 解得 $x \equiv 1 \pmod p$ 或 $x\equiv p - 1 \pmod p

其余两两配对，得 ( p - 1 )! \equiv (p-1) \equiv -1 \pmod p

判定质数：

首先如果 n 为合数，显然存在 n=ij。

我们另 i\le j，得 i\le \sqrt n。

枚举 i，复杂度为 \mathcal{O}(\sqrt n)。

但是这样就显得太落后时代发展，如果 n\le 10^{18} 呢？

考虑 Miller_Rabin 算法。

前置知识：费马小定理。

指的是当 p 为质数时，a^{p-1}\equiv 1\pmod p。

证明在下面的欧拉定理中有写。

令判断的数为 x，显然我们可以找一个质数 p，当 x=p 时，x 为质数，当 p\mid x 时，x 为合数。

然后判断 p^{x-1}\bmod x 是否为 1，如果不是，则 x 必然不是质数。

虽然但是，如果是，x 也必然不是质数。

否则，考虑二次探测定理。

显然 x^2\equiv1\pmod p 时，x\equiv 1\pmod p 或 x\equiv p-1\pmod p。

证明挺简单，这里懒得证。

先用 k 记录 x-1。

然后先将 k 除以 2，令 t=p^k\bmod x。

如果 t\not =1 且 t\not = x-1，则根据二次探测定理，x 不是质数。

若 t=x-1，则无法继续用二次探测定理，认为 x 是质数。

否则一直除，直至 k 为奇数，此时默认其为质数。

很显然这个东西有可能是错的，于是考虑多测几个 p，提高准确率。

复杂度 \mathcal{O}(c\log n)，c 为选的质数个数，总复杂度还是优于 \mathcal{O(\sqrt n)}。

经过检验，选 c 个质数时，如果操作得当，出错的概率仅为 \dfrac{1}{4^c}。

目前没用任何能够低于 \sqrt n 的判断质数的方法，但在 OI 界中，当 n\le 2^{78} 时，取前 12 个质数做 MR 是绝对正确的。

感觉错误概率很可以忽略了。

好像过程并不是不能理解。

LOJ #143 CODE

逆元：

定义：对于两个整数 x,p，若 xy\equiv 1\pmod p 时，则称 y 是 x 的逆元，记做 y=x^{-1}。

求法：当 p 是质数时，y\equiv x^{p-2}\pmod p。

这里的 y 可以使用快速幂计算，而快速幂这种简单的算法想必大家都会。

逆元满足以下几个性质：

证明：采用反证法，假设存在 x,y，满足 x\not= y 且 x,y 的逆元均为 i， xi\equiv yi\pmod p

两边同时除以 i，得出 x\equiv y\pmod p，矛盾。

证明：反证，设存在 x 的逆元，xx^{-1}\equiv1\pmod p

令 xx^{-1}=kp+1,k\in \mathbb{Z}。

设 d=\gcd(x,p)，则 \dfrac{xx^{-1}}{d}=\dfrac{kp+1}{d}

于是同理可得推论 $[1,p)$ 中所有数存在逆元当且仅当 $p$ 为质数。 如果 $p$ 不为质数但是 $\gcd(x,p)=1$，考虑用 exgcd 求逆元。 * 线性求逆元 对于求 $i$ 的逆元： 设 $p=ki+r(0\le k,r<p) k=\lfloor \dfrac{p}{i}\rfloor r=p-ki ki+r\equiv 0\pmod p

同乘 i^{-1}r^{-1}，得 i^{-1}+k\times r^{-1}=0

i^{-1}\equiv -k\times r^{-1} 
for(int i = 2; i <= n; i++) inv[i] = 1ll * (p - p / i) * inv[p % i] % p;

组合数

\binom{n}{m}=\dfrac{n!}{m!(n-m)!}

引理：n\ge m 时，\binom{n}{m}=\binom{n}{n-m}。

帕斯卡法则

根据组合数的定义，显然满足

\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}

二项式定理：

考虑通过组合数的定义证明。

$$ (x+y)^n=\sum\limits_{i=0}^{n}\binom{i}{n}x^iy^{n-i} $$ ## 卢卡斯定理： $$ \binom{n}{m}\bmod p=\binom{\lfloor\dfrac{n}{p}\rfloor}{\lfloor\dfrac{m}{p}\rfloor}\times \binom{n\bmod p}{m\bmod p}\bmod p $$ 证明： 首先 $\binom{p}{f}\equiv 0\pmod p

令 n=sp+q,m=tp+r

(x+1)^n \equiv(x+1)^{sp+q} \equiv((x+1)^p)^s(x+1)^q(1+x^p)^ s(x+1)^q\pmod p \equiv\sum\limits_{i=0}^{s}\binom{s}{i}x^{ip}\sum\limits_{j=0}^q \binom{q}{j} x^j\pmod p $$ \binom{sp+q}{tp+r} $$ 不难发现只有 $i=q,j=t$ 时可以取到系数，故 $$ \binom{sp+q}{tp+r}\equiv\binom{s}{t}\binom{q}{r}\pmod p $$ 得证。 [P3807 CODE](https://www.luogu.com.cn/paste/gwkbplvm) 由于懒得写，用了 Acwing 的模板。 # 欧拉函数 令 $\varphi(n)$ 表示 $1,2,\cdots n$ 中与 $n$ 互质的数。 性质 $1$：若 $p$ 为质数，则 $\varphi(p)=p-1$。 废话。 性质 $2$：$\varphi$ 是积性函数。 前置知识：积性函数。 当 $f(n)$ 满足 $\forall \gcd(p,q)=1,f(pq)=f(p)f(q)$，则称 $f$ 是积性函数。 积性函数的性质： 当 $f,g$ 为积性函数时，则以下函数同样为积性函数： $$ h(x)=f(x^p) $$ $$ h(x)=f^p(x) $$ $$ h(x)=f(x)g(x) $$ $$ h(x)=\sum\limits_{d\mid x}f(d)g(\dfrac{x}{d}) $$ 欧拉函数 $\varphi$、莫比乌斯函数 $\mu$，单位函数 $[A]$、因数个数 $d$ 等都是常见的积性函数。 用 $[n]$ 表示 $\{1,2,\dots, n\}(n>0)$。设 $n$ 有 $k$ 个不同的质因子：$p_1 < p_2 < \dots < p_k$，由容斥原理有 $$ \begin{aligned} \varphi(n) &= \sum_{I\subseteq [k]} (-1) ^{|I|} \frac{n}{\prod_{i\in I}p_i} \\ &= n\sum_{I\subseteq [k]} 1^{n - |I|} \prod_{i\in I} -\frac{1}{p_i} \\ &= n (1 - \frac1{p_1}) ( 1 - \frac1{p_2}) \dots (1 - \frac1{p_k}) \end{aligned} $$ 故得证。 性质 $3$： $$ \sum\limits_{d|n}\varphi(d)=n $$ 考虑 $d\mid n$ 时，$\sum\limits_{i=1}^n [\gcd(n,i)=d]=\varphi(d)

显然 \gcd(n,i)\mid n

所以 \sum\limits_{d|n}\sum\limits_{i=1}^n [\gcd(n,i)=d]=n。

于是 \sum\limits_{d|n}\varphi(d)=n 成立。

欧拉定理：

a^{\varphi(p)}\equiv 1\pmod p

证明：

取模 p 的缩系 a_1,a_2\cdots a_{\varphi(p)}，则 aa_1,aa_2\cdots aa_{\varphi(p)} 也为模 p 的缩系。

于是

\prod\limits_{i=1}^{\varphi(p)}a_i\equiv \prod\limits_{i=1}^{\varphi(p)}\pmod p

得出结论：

a^{\varphi(m)}\equiv 1\pmod p

当 p 为质数时，该定理退化成费马小定理。

a^{p-1}\equiv 1\pmod p

于是费马小定理就不证了。

因此 a^{\varphi(p)}\bmod p=1，于是可得扩展欧拉定理：

$$ a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}\pmod p $$ [P5091 CODE](https://www.luogu.com.cn/paste/xb34l5z3) # 质因数分解： 1. 唯一分解定理 2. Pollard-Rho 算法 这是一个能够找到 $x$ 的素因子的方法。 考虑球出 $x$ 的最大约数 $y$，且 $y\not=x$。 显然你可以 $\mathcal{O}(\sqrt x)$ 试除，但是这个显然严重落后了。 我们考虑找一个 $s$，令 $g=\gcd(s,x)$，如果 $1<g<x$，则找到了一个质因子 $g$，此时将 $g$ 和 $\dfrac{x}{g}$ 递归分解即可。 $\gcd$ 在后文有讲快速求 $\gcd$ 的更相减损术，这个东西能够大大优化。 这里找 $s$ 需要用到随机化。 前置知识：生日悖论 考虑一个班如果有 $x$ 个人，那么这 $x$ 个人中有任意两个人的生日时间相同的概率是多少呢？ 考虑没有人生日相同的概率，显然是 $\prod\limits_{i=1}^{x}\dfrac{365-i+1}{365}$，所以有人生日相同的概率就是 $P(x)=1-\prod\limits_{i=1}^{x}\dfrac{365-i+1}{365}$。 根据这个柿子可以得出，一个班只要有 $23$ 个人，有人生日重复的概率就超过了 $50\%$。当 $x=60$ 时，$P(x)\approx 0.9999$。 考虑令 $v_i=v_{i-1}^2+t\bmod n$ 来生成伪随机数列，$v_0$ 和 $t$ 都是随机数。 然后每次考虑令 $s=|v_i-v_0|$ 进行判断，但是毕竟更相减损术也是 $\mathcal{\log}$ 的，还要继续判断。 如果成环的话可以直接退出，然后修改 $v_0$ 和 $t$ 重新分解。 根据生日悖论，环长最多为 $\mathcal{O}(\sqrt x)$。 你说得对，但是直接爆搜也是 $\mathcal{O}(\sqrt x)$ 的，你这一通操作也没见你优化啊。 这里考虑到这个 $s$ 每次都算 $\gcd$ 有点消耗时间，所以我们累积几次，把 $s$ 相乘并取模，因为取模不会改变 $\gcd$。 那隔的时间如何确定呢？ 考虑倍增优化。 当 $i=2^k,k\in\mathbb{N}$ 时，我们可以令 $v_0=v_i$，然后将累积的 $s$ 算一遍 $\gcd$。 这样可以优化复杂度。 具体我不会证，但是大概在 $\mathcal{O}(n^{\frac{1}{4}})$ 左右，运行起来的效率相当不错。 题外话：由于没有 npy，随机种子用的是我的生日（ [P4718 CODE](https://www.luogu.com.cn/paste/dzy7olaf) # 线性筛 考虑如何判断 $[1,10^8]$ 的所有整数是不是质数，如果 MR 的话很显然会 TLE，考虑如何优化。 我们可以考虑整一个 $\mathcal{O}(n)$ 的算法，对于每个 $i$，将它的倍数全部标记为合数，这样递推下去，复杂度 $\sum\limits_{i=1}^n \dfrac{n}{i}=\mathcal{O}(n\log n)$。 我们考虑到如果一个数轮到它了还没有被标记，说明它是个质数。 显然我们希望对于一个合数，我们只筛一次，这样复杂度就对了。 我们考虑把所有质数都保存下来，存为 $p$，这里的 $p$ 单调上升，每次就标记 $i\times p_j$。 当 $p_j\mid i$ 时，显然之后的 $p_k\times i$ 的最小质因子是 $p_j$ 了，所以此时停止筛。 [P3383 CODE](https://www.luogu.com.cn/paste/gsr9gwav) 然后考虑如何筛 $\varphi$。 当 $i$ 为质数时，$\varphi(i)=i-1$。 接下来继续枚举 $i\times p_j$，如果 $p_j\mid i$，则这个 $\varphi (i\times p_j)$ 怎么求呢？ 考虑推柿子。 $$ \varphi(i\times p_j)=i\times p_j\times \prod \limits_{x\mid p_j\times i\in \mathbb{P}} \dfrac{x-1}{x}=i\times p_j\times \prod \limits_{x\mid i\in \mathbb{P}} \dfrac{x-1}{x} $$ $$ \varphi(i)=i\times \prod \limits_{x\mid i\in \mathbb{P}} \dfrac{x-1}{x} $$ 得 $\varphi(i\times p_j)=\varphi(i)\times p_j$。 否则，$\gcd(i,p_j)=1$，根据 $\varphi$ 时一个积性函数，得 $\varphi(i\times p_j)=\varphi(i)\times \varphi(p_j)=\varphi(i)\times (p_j-1)$。 [P8670 CODE](https://www.luogu.com.cn/paste/49f5ea4g) # 扩展欧几里得 先介绍一下最大公约数。 $\gcd(a,b)$ 表示 $a$ 和 $b$ 的最大公约数，例如 $\gcd(4,12)=4$，$\gcd(54,72)=18,\gcd(15,80)=1$。 注意 $\gcd(0,x)=x$。 考虑用辗转相减法求 $\gcd(a,b)$。 显然 $\gcd(a,b)=\gcd(b,a- b)$ 的证明比较简单，这里不多赘述。 同理得 $\gcd(a,b)=\gcd(b,a\bmod b)$。 复杂度 $\mathcal{O(\log a)}$。 ```cpp int gcd(int a, int b) { while(a && b) { if(a > b) a %= b; else b %= a; } return a + b; } ``` 当然也可以用更相减损术，复杂度不变，但是可以优化常数用。 $$ \gcd(a,b) = \left \{ \begin{aligned} &\gcd(b,a-b)\ && a\bmod 2=1\ b\bmod 2=1 \\ &\gcd(\dfrac{a}{2},b)\ && a\bmod 2=0\ b\bmod 2=1 \\ &\gcd(a,\dfrac{b}{2})\ && a\bmod 2=1\ b\bmod 2=0 \\ &\gcd(\dfrac{a}{2},\dfrac{b}{2})\times 2\ && a\bmod 2=0\ b\bmod 2=0 \\ \end{aligned} \right. $$ 虽然也是 $\mathcal{O}(\log a)$ 的，但是常数明显减小，近似 $\mathcal{O}(1)$。 ```cpp #define ctz __builtin_ctz inline int gcd(int a,int b) { int az = ctz(a), bz = ctz(b), z = (az > bz) ? bz : az, t; b >>= bz; while(a) a >>= az, t = a - b, az = ctz(t), b = min(a, b), a = t < 0ll ? -t : t; return b << z; } ``` 基于值域预处理的快速 $\gcd$： 是一种 $\mathcal{O}(w)$ 预处理，严格 $\mathcal{O}(1)$ 查询的 $\gcd$。 引理： 若一个数 $n$ 存在一组 $a,b,c$，使得 $n=abc,a\le b\le c,a,b\le \sqrt n$，$c\le \sqrt n$ 或者 $c$ 为质数。 证明：考虑使用数学归纳法，$n=1$ 时显然成立。 令 $p$ 为 $n$ 的最小质因数。$a',b',c'$ 为 $\dfrac{n}{p}$ 的一种合法分解。 若 $p\le n^{\frac{1}{4}}$，则 $a'\le (\dfrac{n}{p})^{\frac{1}{3}}$，所以 $pa\le p(\dfrac{n}{p})^{\frac{1}{3}}\le \sqrt n$，所以 $(pa',b',c')$ 是一组符合条件的解。 否则，若 $a'>p$，则 $n=pa'b'c'>p^4>n$，矛盾。故 $a'\le p$，又因为 $p$ 为 $n$ 的最小质因数，故 $a'=1$，$(p,b,c)$ 是一组合法的解。 证明完了，但是好像没啥用啊？？？ 上面的证明也构造了拆 $a,b,c$ 的方法，线性筛一下即可。 在求 $\gcd(n,m)$ 时，可以将答案拆成： $$ \gcd(a,m)\times \gcd(b,m)\times \gcd(c,m) $$ 先求 $a,b$ 的答案，$\gcd(a,m)=\gcd(a,m\bmod a)$。 显然 $a,m \bmod a\le \sqrt n$，所以直接预处理 $\sqrt n$ 以下的 $\gcd$ 即可。 对于 $c$，如果 $c$ 是个质数显然很好求，如果不是则根据引理 $c\le \sqrt n$，套用上面的方法即可。 [P5435 CODE](https://www.luogu.com.cn/paste/j7yz92t5) $1.$ 裴蜀定理： $ax+by=c$ 的充要条件为 $\gcd(a,b)\mid c

证明：

令 $d=\gcd(a,b)$，显然 $d\mid a,d\mid b$，因为 $x,y\in \N^+$，所以 $d\mid ax,d\mid by,d\mid c$，得证。 充分性：由扩展欧几里得算法必然可以构造出 $ax+by=c$ 的解 扩展欧几里得算法： 首先，设 $\gcd(a,b)=g$，于是考虑求解 $ax+by=g$ 的解，解出的解设为 $x_0,y_0$，则原方程的解为 $(\dfrac{x_0c}{g},\dfrac{y_0c}{g})$。 于是现在考虑构造 $ax+by=g$ 的解。 不妨设 $a>b

当 b\mid a 时，解得 x=0,y=1。

根据 \gcd(a,b)=\gcd(b,a\bmod b)，考虑递归解 bx'+(a\bmod b)y'=\gcd(b,a\bmod b)，而右式不变。

由于是递归求解，所以我们假设已知 x',y'，考虑递推回去解原方程 ax+by=\gcd(a,b)。

首先，将取模换成除法。

a\bmod b=a-b\lfloor\dfrac{a}{b}\rfloor

代入，得 bx'+(a-b\lfloor\dfrac{a}{b}\rfloor)y'=\gcd(a,b)

根据乘法分配律得 bx'+ay'-b\lfloor\dfrac{a}{b}\rfloor y'=\gcd(a,b)

带入 ax+by=\gcd(a,b)，得 bx'+ay'-b\lfloor\dfrac{a}{b}\rfloor y'=ax+by

根据等式的性质，得出 x=y',y=x'-b\lfloor\dfrac{a}{b}\rfloor 为原方程的一组特解。

中国剩余定理

给定 n 组非负整数 a_i, b_i ，求解关于 x 的方程组的最小非负整数解。

\begin{cases} x\equiv a_1\pmod {m_1} \\ x\equiv a_2\pmod {m_2} \\ \cdots \\ x \equiv a_n\ \pmod {m_n}\end{cases}

中国剩余定理：

令 M=\prod\limits_{i=1}^{n}m_i\bmod p,M_i=\dfrac{M}{m_i}

设 t_i 为 M_i 以 m_i 为模数的逆元，即 t_iM_i\equiv 1\pmod {m_i}

则 x 的最小非负整数解为

x=\sum\limits_{i=1}^{n}a_it_iM_i\bmod p

证明：

由假设可知，对于所有 i\in\{1,2,\cdots n\}，由于 \forall j\in\{1,2,\cdots n\},j\not =i,\gcd(m_i,m_j)=1，所以可得 \gcd(m_i,M_i)=1，所以必然存在 t_i，满足 t_iM_i\equiv 1 \pmod {m_i}。

再看一下这个式子：

a_it_iM_i

不难发现，t_iM_i\equiv 1\pmod p，所以 a_it_iM_i\equiv a_i\pmod {m_i}。

\forall j\in\{1,2,\cdots n\},j\not =i,a_it_iM_i\equiv 0\pmod {m_j}

所以 x=\sum\limits_{i=1}^{n}a_it_iMi\bmod p 满足

\forall i\in\{1,2,\cdots n\},x\equiv a_it_iM_i+\sum\limits_{j\not=i}a_jt_jM_j\equiv a_i\pmod {m_i}

若 x_1,x_2 均为方程的解，显然 x_1\equiv x_2\pmod M。

于是解集为

\{kM+\sum\limits_{i=1}^{n}a_iy_iM_i\},k\in \mathbb{Z}

练习 P1495

整除分块

引理：

\forall a,b,c\in \mathbb{Z},\left\lfloor\dfrac{a}{bc}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c}}\right\rfloor

证明：

令 \dfrac{a}{b} = \left\lfloor{\dfrac{a}{b}}\right\rfloor + r(0\le r < 1)，则有

\left\lfloor\dfrac{a}{bc}\right\rfloor = \left\lfloor\dfrac{a}{b}\times\dfrac{1}{c}\right\rfloor = \left\lfloor{\dfrac{1}{c}\times\left({\left\lfloor{\dfrac{a}{b}}\right\rfloor + r}\right)}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor\dfrac{a}{b}\right\rfloor}{c} + \dfrac{r}{c}}\right\rfloor = \left\lfloor{\dfrac{\left\lfloor{\dfrac{a}{b}}\right\rfloor}{c}}\right\rfloor

例题 1：

\sum\limits_{i=1}^n\lfloor\dfrac{n}{i}\rfloor

显然直接算是 \mathcal{O(n)} 的，考虑优化。

不难发现有许多 \lfloor\dfrac{n}{i}\rfloor 的值是一样的，而且这些一样的值是呈块状分布。

证明不难，考虑当 i,j>0,i<j 时，\lfloor\dfrac{n}{i}\rfloor\ge \lfloor\dfrac{n}{j}\rfloor。

于是考虑对于每个块的长度和每块中每个数的值求出，就可以直接算贡献了。

如果说一个块的左端点是 l 的话，那么右端点 r 为

\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor

证明：

令 k=\lfloor\dfrac{n}{l}\rfloor。

假如要找到 p，使得 \lfloor\dfrac{n}{p}\rfloor<k，即

\dfrac{n}{p}<k p>\dfrac{n}{k}

所以说，想要找到右端点 r，需要 r\le \dfrac{n}{k}，即 r=\left\lfloor\dfrac{n}{\lfloor\frac{n}{l}\rfloor}\right\rfloor。

接下来是复杂度分析。

考虑整块都可以直接处理，复杂度为 O(\sqrt n)。

证明：令块左端点为 i。

当 i\le \sqrt n 时，总共只有 \sqrt n 个 i。

当 i>\sqrt n 时，\lfloor\dfrac{n}{i}\rfloor< \sqrt n，即 \lfloor\dfrac{n}{i}\rfloor 的种类数不会超过 \sqrt n。

所以复杂度为 \mathcal{O(\sqrt n)}。

long long ans = 0;
for(int l = 1, r; l <= n; l = r + 1) {
    r = n / (n / l);
    ans += 1ll * (r - l + 1) * (n / l);
}

例题 2：

\sum\limits_{i=1}^nk\bmod i

考虑同样的套路：

\sum\limits_{i=1}^nk\bmod i =\sum\limits_{i=1}^n k-i\lfloor\dfrac{k}{i}\rfloor =nk-\sum\limits_{i=1}^n i\lfloor\dfrac{k}{i}\rfloor

然后沿用套路即可，等差数列求和想必大家都会。

例题 3：

P3935 Calculating

不难发现 f(x) 为 d(x)，其中 d(x) 表示 x 的约数个数。

显然 d(n) 是积性函数。所以直接硬上杜教筛。

于是问题就转化成了求：

\sum\limits_{i=1}^n d(i)

考虑对于所有 [1,n] 的正整数 i，其作为约数在 [1,n] 中出现了 \lfloor\dfrac{n}{i}\rfloor 次。

直接套例题 1 即可。

例题 4：

P2260 [清华集训2012] 模积和

考虑先容斥，得原式为

\sum\limits_{i=1}^n\sum\limits_{j=1}^m (n\bmod i)(m\bmod j)-\sum\limits_{i=1}^n (n\bmod i)(m\bmod i) =\sum\limits_{i=1}^n n\bmod i\sum\limits_{j=1}^m m\bmod j-\sum\limits_{i=1}^n (n\bmod i)(m\bmod i)

左边这部分直接套例题 2 即可。

考虑计算

\sum\limits_{i=1}^n (n\bmod i)(m\bmod i) =\sum\limits_{i=1}^n(n-i\lfloor\dfrac{n}{i}\rfloor)(m-i\lfloor\dfrac{m}{i}\rfloor)

展开，得

=\sum\limits_{i=1}^nnm-mi\lfloor\dfrac{n}{i}\rfloor-ni\lfloor\dfrac{m}{i}\rfloor+i^2\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor =n^2m+\sum\limits_{i=1}^n-mi\lfloor\dfrac{n}{i}\rfloor-ni\lfloor\dfrac{m}{i}\rfloor+i^2\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor

整除分块一下即可。注意到

\sum\limits_{i=1}^n i^2=\dfrac{n(n+1)(2n+1)}{6}

CODE

幂

我们定义 a^b 为 b 个 a 相乘，即 a^b = \underbrace{a \times a \times \cdots \times a}_{b \text{ 次}}。

幂满足以下性质：

a^m\times a^n=a^{m+n} \dfrac{a^m}{a^n}=a^{m-n}

那么接下来我们考虑求 a^b \bmod p，其中 b\le 10^9。

显然直接 \mathcal{O(b)} 乘是不行的，考虑利用上面的性质，将 b 拆成 \mathcal{O}(\log b) 个数的和，然后直接乘即可。

考虑将 b 二进制分解，每次 a 自己乘自己，如果说 b 在二进制的这一位是 1 就乘上 a，这样复杂度是 \mathcal{O}(\log b) 的。

比如说，当 a=3,b=6,p=10^9 时：

维护一个答案 q，初始时 q=1。

观察到 b 二进制最后一位不是 1，直接将 a 自乘，此时 a=9,b=3,q=1。

此时 b 二进制最后一位是 1，答案先乘 a，然后将 a 自乘，此时 a=81,b=1,q=9。

最后 b 的二进制还是 1，答案先乘 a，然后将 a 自乘，此时 a=6561,b=0,q=729。

当某些时候快速幂也不管用时，考虑维护一个 \mathcal{O}(1) 的快速幂。

光速幂是指在底数和模数确定时，可以做到 \mathcal{O}(\sqrt w) 预处理，\mathcal{O}(1) 查询的快速幂，w 为指数的范围。

考虑类似于根号分治的思想，如果我们处理出以 1,2,\cdots B 为指数的答案，以及 1,2,\cdots n 中所有 B 的倍数的答案，那么 \forall i\in [1,n]，2^i 都可以利用这两组数据的乘积得出。

复杂度为 \mathcal{O}(B+\dfrac{n}{B})，显然 B=\sqrt n 时复杂度最优。

LOJ #162 CODE

你也可以用类似的方法解决 P5072 [Ynoi2015] 盼君勿忘 的一部分。

BSGS 算法：

阶和原根:

当 a^b\equiv 1\pmod p 时，且此时 b 是满足这一条件的最小正整数解，我们称 a 膜 p 的阶为 b。记作 \delta_p(a)。

四个性质：

考虑反证法，设 a^i\equiv a^j\pmod p,i,j\le \delta_p(a)，则 a^{j-i}\equiv 1\pmod p，j-i<\delta_p(a)，与最小性矛盾。

  1. 若 a^x\equiv 1\pmod p，则 \delta_p(a)\mid x。

令 y=\delta_p(a)。

继续考虑反证法，令 x=ky+b,b<y。

则 a^b\equiv a^{ky}\times a^b\equiv 1\pmod p，与阶的最小性矛盾。

  1. 若 \gcd(a,p)=\gcd(b,p)=1，则 \delta_p(a)\delta_p(b)=\delta_p(ab) 的充要条件是 \gcd(\delta_p(a),\delta_p(b))=1。

必要性：

显然 a^{\delta_p(a)}\equiv b^{\delta_p(b)}\equiv 1\pmod p。

所以 ab^{\operatorname{lcm}(\delta_p(a),\delta_p(b))}\equiv 1\pmod p。

由性质二得 \delta_p(ab)\mid \operatorname{lcm}(\delta_p(a),\delta_p(b))。

即 \delta_p(a)\delta_p(b)\mid \operatorname{lcm}(\delta_p(a),\delta_p(b))。

又因为 \delta_p(a)\delta_p(b)=\operatorname{lcm}(\delta_p(a),\delta_p(b))\times \gcd(\delta_p(a),\delta_p(b))，

所以 \gcd(\delta_p(a),\delta_p(b))=1。

充分性：

(ab)^{\delta_p(ab)}\equiv 1\pmod p (ab)^{\delta_p(ab)\delta_p(b)}\equiv 1\pmod p a^{\delta_p(ab)\delta_p(b)}\equiv 1\pmod p \delta_p(a)\mid \delta_p(ab)\delta_p(b)

又因为 \gcd(\delta_p(a),\delta_p(b))=1，得 \delta_p(a)\mid \delta_p(ab)。

同理可得 \delta_p(b)\mid \delta_p(ab)。

由于 \gcd(\delta_p(a),\delta_p(b))=1，则 \delta_p(a)\delta_p(b)=\delta_p(ab)。

重新推一遍：

(ab)^{\delta_p(ab)}\equiv 1\pmod p (ab)^{\delta_p(a)\delta_p(b)}\equiv 1\pmod p (a^{\delta_{p}(a)})^{\delta_p(b)} (b^{\delta_p(b)})^{\delta_p(a)}\equiv 1\pmod p

得 \delta_p(ab)\mid \delta_p(a)\delta_p(b)。

结合上式，得 \delta_p(a)\delta_p(b)=\delta_p(ab)。

性质 4：

若 \gcd(a,p)=1，则 \delta_p(a^k)=\dfrac{\delta_p(a)}{\gcd(\delta_p(a),k)}。

证明：

a^{k\delta_p(a^k)}=(a^k)^{\delta_p(m)\delta_p(a^k)}\equiv 1\pmod p\\ \delta_p(a)\mid k\delta_p(a^k)\\ \dfrac{\delta_p(a)}{\gcd(\delta_p(a),k)}\mid \delta_p(a^k)

又有

(a^k)^{\frac{\delta_p(a)}{\gcd(\delta_p(a),k)}}=(a^{\delta_p(a)})^{\frac{k}{\gcd(\delta_p(a),k)}}\equiv 1\pmod p \delta_p(a^k)\mid \dfrac{\delta_p(a)}{\gcd(\delta_p(a),k)}

综上，\delta_p(a^k)=\dfrac{\delta_p(a)}{\gcd(\delta_p(a),k)}。

原根：若 \varphi(m)=\delta_m(a) 且 \gcd(a,m)=1，则我们称 m 是 a 的原根。

一个数 x 存在原根当且仅当 x\in \{2,4,p^k,2p^k\}，其中 k 为正整数。

显然若一个数 g 为 m 的原根，则 g,g^2,\cdots g^{\varphi(m)}构成模 m 意义下的既约剩余系，由于 \gcd(g,m)=1，所以 \gcd(g^x,m)=1，且剩余系各个数互不相等。

由于性质一，原根一定在 g,g^2,g^3\cdots g^{\varphi(m)} 之间。

王元于 1959 年证明了，若 m 有原根，则最小原根是 m^{0.25} 级别的，所以我们可以直接枚举最小原根 g。

线性筛 \varphi，然后枚举 k，排个序输出即可。

P6091 CODE

二次剩余：

例题：P5491 【模板】二次剩余

介绍一个 Cipolla 算法。

首先，你必须判断这玩意有没有解。

我们称这个方程有解，则 n 是模 p 的二次剩余，无解则称 n 是模 p 的非二次剩余。

先引入个勒让德符号遮盖 s5o 没啥实力的事实

(\dfrac{n}{p})=\begin{cases}1,\ \ \ n是二次剩余 \\ 0,\ \ \ n\equiv 0\pmod p \\ -1 \ \ n是非二次剩余\end{cases}

欧拉准则可以解决判定的问题。

根据费马小定理也可以是欧拉定理有 n^{p-1}\equiv 1\pmod p，开始推式子：

n^{2(\frac{p-1}{2})}\equiv 1\pmod p\\(n^{\frac{p-1}{2}}+1)(n^{\frac{p-1}{2}}-1)\equiv 0\pmod p

欧拉准则：(\dfrac{n}{p})\equiv n^{\frac{p-1}{2}}\pmod p

也就是说 n 是模 p 的二次剩余的 n^{\frac{p-1}{2}}\equiv 1\pmod p 的充要条件。

充分性：

当 x^2\equiv n\pmod p 成立时，有 n^{\frac{p-1}{2}}\equiv x^{p-1}\equiv p。

必要性：

设 g 为 p 的一个原根（质数必定有原根），令 n=g^k（\gcd(n,p)=1 所以可以这样表示）

则 n^{\frac{p-1}{2}}\equiv 1\equiv g^{\frac{k}{2}(p-1)}\pmod p

由欧拉定理得 \varphi(p)\mid \dfrac{k}{2}(p-1)

所以 k 是偶数，此时令 x=g^{\frac{k}{2}} 即成立。

显然剩下一种 p\mid n 也是成立的。

解的数量：

对于 n\equiv x^2\pmod p，令其有不相等两根 x_1,x_2，则

x_1^2\equiv x_2^2\pmod p\\(x_1-x_2)(x_1+x_2)\equiv 0\pmod p

由于 x_1\not = x_2，所以 x_1+x_2\equiv 0\pmod p

所以该方程只有两个解且它们互为相反数。

因此模 p 意义下共有 \dfrac{p-1}{2} 个二次剩余。

接下来考虑 Cipolla 算法。

先找到一个数 a 使得 a^2-n 不是二次剩余，令 i^2\equiv a^2-n\pmod p，则 (a+i)^{\frac{p+1}{2}} 是一个解，其相反数就是另一个解。

这个 i 有点类似于复数中的虚部，a 为实部。

证明：

(a+i)^{p+1}\\ =(a+i)(a+i)^p\\ =(a+i)(a^p+i^p)\\ =(a+i)(a-i)\\ =a^2-i^2\\ =a^2-(a^2-n)=n

第二步可以通过二项式定理得到只有 \binom{0}{p} 和 \binom{p}{p} 是不被约掉的。

第三步由费马小定理可得 a^p\equiv a\pmod p

然后大概就做完了。

由于大约有 \dfrac{p}{2} 个数有二次剩余，所以期望 2 次就能得到 a。

P5491 CODE

为了反驳 @hh弟中弟 的评论，我放一句不对的话：