同余数论乱讲

对最近学的数论知识做一些总结，内容比较杂乱，包括但不限于中国剩余定理、欧拉定理、阶和原根、二次剩余。

想不到一写又是 4k 字，害怕害怕……

线性同余方程

先从不定方程开始扯。给出一个形式化的定义：我们称关于 $x,y$ 的，形如 $ax+by=c$ 的方程为二元一次不定方程。

• （裴蜀定理）关于 $x,y$ 的，形如 $ax+by=(a,b)$ 的不定方程总存在整数解。

可以简单推广出一个普遍性的结论：对于不定方程 $ax+by=c$，它存在整数解的充要条件是 $(a,b)|c$，证明如下：

1. （充分性）$ax+by=c\Rightarrow ax/(a,b)+by/(a,b)=c/(a,b)$

2. （必要性）根据裴蜀定理，可以构造 $x’,y’$ 使得 $ax’+by’=(a,b)$，那么有 $x=cx’/(a,b),y=cy’/(a,b)$

显然一个线性同余方程 $ax\equiv b\text{ }(\text{mod }p)$ 可以看作不定方程 $ax+tp=b$，其中 $x,t$ 是未知量。根据上面的推导，可以得到该方程存在解的充要条件是 $(a,p)|b$。注意这个条件的本质实际上是 $(a,p)|(b,p)$。

这个条件启发我们，如果 $ax\equiv b\text{ }(\text{mod }p)$有解，那么它可以被改写作 $ax/(a,p)\equiv b/(a,p)\text{ }(\text{mod } p/(a,p))$。

逆元

如果存在一个 $x\in \mathbb F_p$，使得 $ax\equiv 1\text{ }(\text{mod }p)$，那么称 $x$ 是 $a$ 在 $\mathbb F_p$ 下的逆元，记作 $x= a^{-1}\bmod p$。

根据上面的推导，$a$ 在 $\mathbb F_p$ 下的逆元存在当且仅当 $(a,p)=1$，即 $a,p$ 互质。

考虑模合数的剩余系下，只有一些数字存在逆元，因此在 OI 中，需要求模合数的逆元的情况比较少见。这一类情况需要用到扩展欧几里得算法，相关资料可以在博客中找到。

对于模质数的逆元，会在下面进一步讨论。

中国剩余定理

中国剩余定理给出了一组线性同余方程的解在某种意义下的近似，其中“某种意义”特指对所有方程的模数的 LCM 取模。

形式化地，对于 $n$ 条关于 $x$ 的线性同余方程，第 $i$ 条形如 $a_ix\equiv b_i\text{ }(\text{mod }p_i)$，那么中国剩余定理给出了如下求解 $x$ 的方法：

令 $P=\prod\limits_{i=1}^n p_i$，记 $k_i=P/p_i,k^{-1}_i=k_i^{-1}\bmod p_i$，计算 $x=\prod\limits_{i=1}^n k_ik^{-1}_i\bmod P$。需要特别注意的是，这里模数的变化是很关键的。

欧拉定理

欧拉定理指出，如果 $(a,p)=1$，那么有：

$$a^{\varphi(p)}=1\text{ }(\text{mod }p)$$

特别的，如果 $p$ 是质数，那么 $\varphi(p)=p-1$，有 $a^{p-1}=1\text{ }(\text{mod }p)$，这样就得到了费马小定理。这可以用来求逆元：$a·a^{p-2}\equiv 1\text{ }(\text{mod }p)$。

通过欧拉定理可以简单得到，如果 $(a,p)=1$，那么对任意 $n\in \mathbb N$，存在：

$$a^n\equiv a^{n\bmod \varphi(p)}\text{ }(\text{mod }p)$$

这指出了在剩余系下，与模数互质的数的幂次是成环的。这个环将会在下面对阶和原根的讨论中反复出现。

注意上面的柿子还有一个推广形式，即对 $(a,p)>1,n>\varphi(p),n\in \mathbb N$，存在：

$$a^n\equiv a^{n\bmod \varphi(p)+\varphi(p)}\text{ }(\text{mod }p)$$

这意味着只有当 $n$ 足够大的时候，它才会进入一个环。

阶和原根

• （阶）对于 $(a,p)=1$，必然存在至少一个 $c\in \mathbb N^+$，使得 $a^c\equiv 1\text{ }(\text{mod }p)$。我们称满足条件的最小的 $c$ 为 $a$ 模 $p$ 的阶，记作 $c=\text{ord}_pa$。

考虑阶的实际意义：欧拉定理指出了一个与模数互质的数的幂次会成环，并且给出了环长的上界，而阶更精确地确定了这个环长是多少。

• （原根）对于 $g\in \mathbb F_p$，如果 $\text{ord}_pg=\varphi(p)$，则称 $g$ 是模 $p$ 的原根。

原根的特殊之处在于，原根的环是该剩余系下一个数的幂次可以得到的最大的环，原根的幂次可以填充整个简化剩余系。或者说我们可以用原根定义离散对数，即设 $\log_g x=t$，其中 $t\in \mathbb F_p$，是唯一的满足 $g^t\equiv x\text{ }(\text{mod }p)$ 的数。

注意原根不能填充整个剩余系。这意味着对于非质数模数，即便是正数的离散对数也可能不存在。

更加深刻的取理解阶和原根，可以发现一个数 $a$ 的幂次形成的环，实际上就是原根以 $(\log a,\varphi(p))$ 为步长走过的环上的点。形式化的，对于 $(a,p)=1$，$a^n\bmod p,n\in\mathbb N$ 的所有取值是：

$$g^{kt},t=(\log a,\varphi(p)),k\in[0, \text{ord}_pa)$$

也可以简单归纳出阶的一些性质：

$$\begin{aligned} &\text{ord}_pa|\varphi(p)\newline&\text{ord}_pa^k=\dfrac{\text{ord}_pa}{(\text{ord}_pa,k)} \end{aligned}$$

计算阶和原根

注意到 $\text{ord}_pa|\varphi(p)$，因此直接暴力枚举 $\varphi(p)$ 的因数，就可以做到 $O(\sqrt p)-O(d(\varphi(p)))$ 计算阶，实现的好就是 $O(p^{1/4})-O(d(\varphi(p)))$。

可以证明，一个数 $m$ 存在原根的充要条件是 $m=2,4,p^\alpha,2p^\alpha$，其中 $p$ 是奇素数，$\alpha\in \mathbb N^+$ 。

可以证明，如果一个数存在原根，那么这个数的最小原根是 $m^{1/4}$ 级别。

原根有着这样的一个判定方法，即 $g$ 是原根等价于 $\forall i,g^{\varphi(p)/\rho_i}\not\equiv 1\text{ }(\text{mod }p)$，其中 $\rho_i$ 是 $\varphi(p)$ 的质因子。

因此直接暴力枚举判断就可以找到最小原根，期望复杂度 $O(p^{1/4}\log^2 p)$。

可以证明，设 $g$ 是 $p$ 的一个原根，那么集合 $\begin{Bmatrix}g^s\bmod p\text{ | }s\in\mathbb N,(s,\varphi(p))=1\end{Bmatrix}$ 给出了 $p$ 的所有原根。

BSGS

北上广深（Baby Step Giant Step, BSGS）算法是一个可以在 $O(\sqrt p)$ 的时间内，求解模任意 $p\in \mathbb N^+$ 的离散对数的算法。形式化地，即解这样一个方程：

$$a^x\equiv b\text{ }(\text{mod }p)$$

可以设阀值 $B$，令 $x=kB-r$，有 $(a^B)^k\equiv ba^r\text{ }(\text{mod }p)$。我们用哈希表预处理 $a^{kB}$ 的所有可能取值以及对应的 $k$，那么只需要枚举 $r$，查找一个 $k$ 即可。

注意 $a^{kB}\equiv ba^r\text{ }(\text{mod }p)$ 是 $a^{kB-r}\equiv b(\text{mod }p)$ 的必要不充分条件，因此还需要检验一下得到的解是否可行。特别地，当 $p$ 是质数时，转化有充分性，可以不进行特判。

注意 $a^{kB}\to k$ 是单射，因此理论上需要记录前两个值，但是毛估一下会发现只记录一个值的错误概率很低。

欧拉定理给出了 $x$ 的上界即 $2\varphi(p)$，取 $B=\lceil\sqrt {2p}\rceil$，可以得到最优复杂度 $O(\sqrt p)$。

代码可以在模板梳理中找到。

二次剩余

• （二次剩余）对于一个数 $n$ 满足 $p\nmid n$，如果存在一个 $x\in \mathbb F_p$ 使得 $x^2\equiv n\text{ }(\text{mod }p)$，那么称 $n$ 是模 $p$ 的二次剩余；否则，则称 $n$ 是模 $p$ 的非二次剩余。

可以证明，如果不考虑 $0$，那么一个数的二次剩余和非二次剩余各有恰 $\dfrac{p-1}{2}$ 个。

• （勒让德符号）定义一个数 $n$ 模 $p$ 的勒让德符号 $(\frac{n}{p})$ 是一个在 $-1,0,1$ 之间的整数。定义当 $p|n$ 时 $(\frac{n}{p})=0$，当 $n$ 是模 $p$ 的二次剩余时 $(\frac{n}{p})=1$，否则 $(\frac{n}{p})=-1$。
• （欧拉判别准则）$\left(\dfrac{n}{p}\right)\equiv n^{(p-1)/2}\text{ }(\text{mod }p)$

以上三条给出了二次剩余的定义以及判定方法。如果以及判定了 $n$ 是二次剩余，这意味着 $x^2=n\text{ }(\text{mod }p)$ 将会有解，接下来我们讨论解这个同余二次方程。

首先考虑解的数量。假设存在任意多的解，取其中不相等的两个 $x_0,x_1$，那么有：

$$\begin{aligned} &x_0^2\equiv x_1^2 &\text{ }(\text{mod }p)\newline \Leftrightarrow &(x_0-x_1)(x_0+x_1)\equiv0&\text{ }(\text{mod }p)\end{aligned}$$

考虑 $x_0\neq x_1$，那么必然有 $x_0+x_1\equiv 0\text{ }(\text{mod }p)$，也就是说互不相同的两个解必然互为相反数。这同时可以说明，这个方程至多有两个解。

Cipolla 算法可以在模质数的前提下求出其中的一个解。

Cipolla’s Algorithm

设 $p$ 是一个质数，考虑找到一个数 $a$，使得 $a^2-n$ 是模 $p$ 的二次非剩余。由于随机一个数有 $1/2$ 的概率是二次非剩余，那么只需要期望两次操作就可以找到。

定义虚数单位 $\text i$ 为满足 $\text i^2=a^2-n$ 的数，在模意义下建立一个类复数域，有 $x\equiv (a+\text i)^{(p+1)/2}\text{ }(\text{mod }p)$，证明如下：

$$\begin{aligned} (a+\text i)^{(p+1)/2}&\equiv [(a+\text i)(a+\text i)^p]^{1/2} &\text{ }(\text{mod }p)\newline &\equiv [(a+\text i)(a^p+\text i^p)]^{1/2}&\text{ }(\text{mod }p)\newline &\equiv [(a+\text i)(a-\text i)]^{1/2}&\text{ }(\text{mod }p)\newline &\equiv (a^2-\text i^2)^{1/2}\equiv n^{1/2}&\text{ }(\text{mod }p)\end{aligned}$$

这是因为有 $a^p\equiv a·a^{p-1}\equiv a\text{ }(\text{mod }p)$，并且 $i^p\equiv i(i^2)^{(p-1)/2}\equiv i(a^2-n)^{(p-1)/2}\equiv -i\text{ }(\text{mod }p)$，并且 $(a+b)^p\equiv a^p+b^p\text{ }(\text{mod }p)$。

那么只需要实现一个复数类，做快速幂即可，复杂度 $O(\log p)$。代码可以在模板梳理中找到。

高次剩余

在模质数的意义下，求解形如 $x^a\equiv n\text{ }(\text{mod }p)$ 有一类简单且普适性的 $O(\sqrt p)$ 求解方法。具体如下：

因为是模质数，所以简化剩余系下只有 $0$ 没有被覆盖。如果 $x=0$，那么已经做完了，否则 $x$ 的离散对数一定存在。此时可以认为 $n\neq 0$，对两边同时取离散对数，我们可以得到：

$$a\log x\equiv \log n\text{ }(\text{mod }\varphi(p))$$

实则是一个不定方程，可以直接求解。因此复杂度只有计算离散对数的 $O(\sqrt p)$。如果 $p$ 很小，也可以直接预处理离散对数，那么回答的复杂度应该不会高于 $\log p$。

一道栗题

给定一个数字 $n$，判断其是否为完全平方数。 $n\le 10^{1000000}$

直接大力高精度开根，存在 $O(n\log n)$ 的牛顿迭代做法，但是细节太多。比较容易理解的是 $O(n\log^2 n)$ 做法，即朴素牛迭，不过要借助 $O(n\log n)$ 高精度整除的科技。这都不太好做。

考虑随机一个质数 $P$，如果 $P\nmid n$，那么 $n$ 是完全平方等价于 $n$ 是模 $p$ 的二次剩余，使用欧拉准则判断即可。由于不一定满足 $P\nmid n$，所以多随机几个即可。

又一道栗题

给定一个长度为 $n$ 的序列 $\left\langle a\right\rangle$。有 $q$ 次操作，分为两种类型：

• 修改操作每次给定区间 $[l,r]$，令这一段区间内的每个元素执行操作 $a’_i\gets c^{a_i}\bmod p$，其中 $c,p$ 在所有操作开始前给出。
• 询问操作给出区间 $[l,r]$，你需要求出 $[l,r]$ 内所有 $a_i$ 的和对 $p$ 取模的值。

$n,q\le 5\times 10^4, p\le 10^8$

一般来说这种奇怪数据结构题都可以直接做。

考虑构造一个序列，满足 $b_0=a_i,b_j=c^{b_{j-1}}(j>0)$。根据欧拉定理，第 $j$ 项的值可以这样算出来：计算 $d_0=b_0\bmod\varphi_j(p)$，然后带入第一项计算 $d_1=c^{d_0}\bmod \varphi_{j-1}(p)$，然后带入第二项计算 $d_2=c^{d_1}\bmod \varphi_{j-2}(p)$…

其中 $\varphi_1(p)=\varphi(p),\varphi_j(p)=\varphi(\varphi_{j-1}(p))(j>1)$。容易发现当 $j$ 达到 $\log p$ 的级别的时候，会存在一个分界点，使得从这里往后的 $\varphi_j(p)$ 总等于 $1$。

因此只需要大力维护连续段即可，考虑到快速幂的复杂度，用线段树维护就是 $O(n\log n\log ^2p)$，并查集的话就是 $O(n\alpha(n)\log^2p)$。这里我用线段树实现的，常数大的一匹…

#include<bits/stdc++.h>
using namespace std;
#define lc k << 1
#define rc k << 1 | 1
const int CN = 5e4 + 10;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
void write(int x) {if(x > 9) write(x / 10); putchar('0' + x % 10);}
int P, d[101]; bool flag;
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int qp(int a, int b, int p){
    int r = 1; bool fla = a >= p; a %= p; 
    for(; b; b >>= 1){
        if(b & 1){
            flag |= fla;
            if(1ll * r * a >= p) flag |= 1;
            r = 1ll * r * a % p;
        }
        if(1ll * a * a >= p) fla |= 1;
        a = 1ll * a * a % p;
    }
    return r;
}
int n, q, c, a[CN], len[CN], fac[50];
int varphi(int x){
    fac[0] = 0; int t = x;
    for(int d = 2; d * d <= x; d++){
        if(t % d) continue;
        fac[++fac[0]] = d; while(!(t % d)) t /= d;
    }
    if(t ^ 1) fac[++fac[0]] = t;
    int res = x;
    for(int i = 1; i <= fac[0]; i++) res = res / fac[i] * (fac[i] - 1);
    return res;
}
int sum[CN << 2], cnt[CN << 2]; 
void pu(int k) {sum[k] = add(sum[lc], sum[rc]), cnt[k] = cnt[lc] + cnt[rc];}
void bd(int l, int r, int k){
    if(l == r) return (void)(cnt[k] = 1, sum[k] = a[l]);
    int m = (l + r) >> 1; bd(l, m, lc), bd(m + 1, r, rc), pu(k);
}
void upd(int l, int r, int k){
    if(!cnt[k]) return;
    if(l == r){
        len[l]++; if(len[l] == d[0]) cnt[k]--;
        int alp = a[l] % d[len[l]]; flag = a[l] >= d[len[l]]; 
        for(int p = len[l] - 1; p; p--){
            if(!flag) alp = qp(c, alp, d[p]);
            else alp = qp(c, alp + d[p + 1], d[p]);
        }
        sum[k] = alp; return;
    }
    int m = (l + r) >> 1;
    upd(l, m, lc), upd(m + 1, r, rc), pu(k);
}
void md(int l, int r, int k, int s, int t){
    if(s <= l && r <= t) return upd(l, r, k);
    int m = (l + r) >> 1;
    if(s <= m) md(l, m, lc, s, t);
    if(m < t) md(m + 1, r, rc, s, t);
    pu(k);
}
int qu(int l, int r, int k, int s, int t){
    if(s <= l && r <= t) return sum[k];
    int m = (l + r) >> 1, res = 0;
    if(s <= m) res = add(res, qu(l, m, lc, s, t));
    if(m < t) res = add(res, qu(m + 1, r, rc, s, t));
    return res;
}
int main(){
    n = read(), q = read(), P = read(), c = read();
    d[d[0] = 1] = P; 
    while(d[d[0]] ^ 1) d[d[0] + 1] = varphi(d[d[0]]), d[0]++; 
    d[++d[0]] = 1;
    for(int i = 1; i <= n; i++) len[i] = 1, a[i] = read();
    bd(1, n, 1);
    while(q--){
        int tp = read(), l = read(), r = read();
        if(tp) write(qu(1, n, 1, l, r)), puts("");
        else md(1, n, 1, l, r);
    }
    return 0;
}

双一道栗题

有 $n$ 个互不相等的整数 $a_1, a_2, \cdots, a_n$，系统会从中随机选择若干个，而你需要确定所有选出的数字。
你可以进行若干次询问，每次给出一个 $k$。如果 $a_k$ 被选择，那么系统会将所有选出的数中，能被表示成 $a_k^m\bmod p\text{ }(k\in\mathbb N^+)$ 的形式的数字告诉你。
如果系统的每次选择是等概率选一个集合，请你求出你的最小询问次数的期望，对 $998244353$ 取模。

$n\le 5000, 0<a_i<p\le 10^8$
$\text{Subtask1(50pts) : } p \text{ is prime}$
$\text{Subtask2(50pts) : } p=q^k, \text{ where }q\text{ is prime}$

显然这是计数题不是期望题，考虑简单转化之后，只需要求所有情况下最小操作次数的和。

用 $u\to v$ 的一条边表示 $u$ 经过一通操作之后可以变成 $v$，那么得到一张可能有环的有向图。不妨钦点对于一个等价集合，只用标号最小的那个算一次贡献，那么图上的环没有了。枚举一个点算贡献，设 $cnt$ 表示图上能到达这个点的点的数量（包括自身），那么这部分贡献就是 $2^{n-cnt}$。

考虑暴力枚举 $i,j$，如何判断一条边 $i\to j$ 存在。不考虑 $0$，由于 $p$ 是质数，那么意味着剩余系下每个数的阶都存在，离散对数也存在。那么柿子变成 $m\log a_i\equiv a_j\text{ }(\text{mod }\varphi(p))$，有解等价于 $(\log a_i,\varphi(p))|\log a_j$，等价于 $(\log a_i,\varphi(p))|(\log a_j, \varphi(p))$。考虑 $\log a_i$ 实际上描述了 $a_i$ 每次在原根形成的环上走过的步长，那么有 $(\log a_i,\varphi(p))\text{ord}_p a_i=\varphi(p)$，柿子又变成 $\text{ord}_p a_j|\text{ord}_p a_i$。

那么只需要 $O(\sqrt p)$ 预处理因子，求阶就是 $O(d(\varphi(p))\log p)$ 的，这样就有复杂度 $O(n^2+nd(\varphi(p))\log p)$。

考虑如果 $p=q^k$，这意味着不在简化剩余系里面的数字是不存在阶和离散对数一说的。考虑把数分解成 $a_i=q^{\alpha_i}\beta_i$，然后分类讨论：

1. $\alpha_i=\alpha_j=0$，变成上面的情况；
2. $\alpha_i,\alpha_j > 0$，那么可以直接解出来 $m=\alpha_j/\alpha_i$，快速幂判断即可；
3. 否则，由于 $q$ 这一个质因子无论如何不会出现或者消失，那么总是不行的。

那么这样就有复杂度 $O(n^2\log p)$。

#include<bits/stdc++.h>
using namespace std;
const int P = 998244353;
const int CN = 5050;
int read(){
    int s = 0, ne = 1; char c = getchar();
    for(;c < '0' || c > '9';c = getchar()) if(c == '-') ne = -1;
    for(;c >= '0' && c <= '9';c = getchar()) s = (s << 1) + (s << 3) + c - '0';
    return s * ne;
}
int add(int x, int y) {return x + y >= P ? x + y - P : x + y;}
int n, p, q = 1, K, fac[CN], ord[CN], A[CN], a[CN], b[CN], ans, p2[CN]; // A[i] = a[i]q^b[i]
int qp(int a, int b){
    if(b < 0) return 1; int r = 1;
    for(; b; b >>= 1, a = 1ll * a * a % p) if(b & 1) r = 1ll * r * a % p;
    return r;
}
void div(int n){
    for(int d = 1; d * d <= n; d++){
        if(n % d) continue;
        fac[++fac[0]] = d, fac[++fac[0]] = n / d;
    }
    sort(fac + 1, fac + fac[0] + 1), fac[0] = unique(fac + 1, fac + fac[0] + 1) - fac - 1;
}
bool ck(int u, int v) { // u to v
    if(!b[u] && !b[v]){
        if(ord[u] == ord[v]) return u < v;
        return !(ord[u] % ord[v]);
    }
    else if(b[u] && b[v]){
        if(u == v || b[v] % b[u]) return 0;
        return qp(A[u], b[v] / b[u]) == A[v];
    }
    else return 0;
}
int main(){
    n = read(), p = read();
    for(int i = 2; q == 1 && i * i <= p; i++) if(!(p % i)) q = i;
    int t = p; while(q ^ 1 && !(t % q)) K++, t /= q; div(p - qp(q, K - 1));
    for(int i = 1; i <= n; i++){
        A[i] = a[i] = read(); while(q ^ 1 && !(a[i] % q)) b[i]++, a[i] /= q;
    }
    for(int i = 1; i <= n; i++) for(int j = 1; !ord[i] && j <= fac[0]; j++)
        if(qp(a[i], fac[j]) == 1) ord[i] = fac[j];
    p2[0] = 1; for(int i = 1; i <= n; i++) p2[i] = add(p2[i - 1], p2[i - 1]);
    for(int i = 1; i <= n; i++){
        int cnt = 0;
        for(int j = 1; j <= n; j++) cnt += ck(j, i);
        ans = add(ans, p2[n - cnt - 1]);
    }
    printf("%d\n", ans);
    return 0;
}

相关题目

1. 暂无来源
2. 「SHOI2017」相逢是问候
3. 「WC2020」猜数游戏