同余 #2

$\text{JK_Lover}$ 大帝亲自辅导。

Exgcd

给定 $a,b$ ,求解不定方程 $ax+by=\gcd(a,b)$ 的整数解的算法。已知,当 $ax+by=c$ 有解时,当且仅当 $\gcd(a,b)|c$ 满足时。

我们通过 $bx’+(a\%b)y’=\gcd(b,a\%b)$ 来求解该方程,这个过程与求 $\gcd(a,b)$ 是类似的。而在 $b=0$ 的时候,明显有一组解为 $x=1,y=0$ 。那么,我们从 $bx’+(a\%b)y’=\gcd(b,a\%b)$ 的解 $x=x’,y=y’$ 来递归求解,将 $a\%b$ 展开为 $a-b\times \lfloor \frac{a}{b}\rfloor$ ,将该式带回原式,整理出 $a$ 和 $b$ 的系数,得到 $ay’+b(x’-\lfloor\frac{a}{b}\rfloor\times y’)=\gcd(b,a\%b)=\gcd(a,b)$ ,从而得到 $x=y’,y=x’-\lfloor\frac{a}{b}\rfloor\times y’$ 。

而对于一般解 $ax+by=c$ 的方程,有 $k=\frac{c}{\gcd(a,b)}$ ,则用 $\text{exgcd}$ 求出一组解之后再将 $x,y$ 扩大 $k$ 倍即可。

时间复杂度同 $\gcd(a,b)$ 为 $\mathcal O(\log \min(a,b))$ 。


逆元

如果有 $ax\equiv 1 \pmod m$ 成立,则 $a$ 是 $x$ 在模 $m$ 意义下的逆元。记作 $x^{-1}$ ,后也记作 $inv(x)$ 。

模数为质数的求法

有费马小定理:$x^{m-1}\equiv 1\pmod m$ ,而显然, $x^{m-2}\times x^{1}\equiv 1\pmod m$ ,那么, $x^{x-2}$ 就是 $x$ 在模 $m$ 意义下的逆元。在使用快速幂的前提下的时间复杂度为 $\mathcal O(\log m)$ 。

线性递推式

首先有 $inv(1)=1$ ,对于 $x>1$ 有 $\lfloor\frac{m}{x}\rfloor\times x+(m\%x)\equiv 0\pmod m$ ,然后得到式子 $(m\%x)\equiv m-\lfloor\frac{m}{x}\rfloor\times x\pmod m$ ,然后在式子两端同时乘上 $inv(x)\times inv(m\%x)$ 得到:

$inv(x)\equiv inv(m\%i)\times (m-\lfloor\frac{m}{i}\rfloor)\pmod m$

这样就得出了逆元的线性递推式。这种方法只能用于 $m$ 是质数的情况,且限制情况较多。

此情况的时间复杂度是 $\mathcal O(n)$ 。


CRT

中国剩余定理($\text{Chinese Remainder Theorem}$),用于求解满足:

其中 $m_1,m_2…m_k$ 两两互质(但不一定是质数),的最小的 $x$ 值。

设 $M=\prod m_i$ ,利用 $\text{exgcd}$ 求出 $\frac{M}{m_i}$ 的逆元,记为 $p_i$ ,求出一个数 $x_i=\frac{M}{m_i}\times p_i$ ,所以有 $x_i\times a_i\equiv 1\pmod{m_i}$ 且 $x_i\times a_i\equiv 0\pmod{m_j},i\ne j$ ,此时构造出的 $X_i=x_i\times a_i$ 满足了第 $i$ 个方程的限制,且不影响其他方程。那么合并方程解得到 $x=\sum x_i\times a_i\pmod M$ 即可。

$\text{CRT}$ 的时间复杂度为 $\mathcal O(n\log M)$ 。


EXCRT

扩展中国剩余定理,与 $\text{CRT}$ 求解一样的同余方程组,但 $m_1,m_2…m_k$ 不要求两两互质。

不断将两个同余方程合并为一个等价的同余方程:

对于 $x\equiv a_1\pmod{m_1},x\equiv a_2\pmod{m_2}$ ,将同余方程转化成不定方程,变成 $x=a_1+k_1\times m_1=a_2+k_2\times m_2$ ,得到 $k_2m_2-k_1m_1=a_1-a_2$ ,通过 $\text{Exgcd}$ 求得 $k_1,k_2$ ,然后代入求得 $x\equiv a_1+k_1m_1\pmod{\text{lcm}(m_1,m_2)}$ ,这就是合并的结果。最后得到一个方程时得到通解。

$\text{ExCrt}$ 的时间复杂度也是 $\mathcal O(n\log M)$ 。

模板

P4777 【模板】扩展中国剩余定理(EXCRT)

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
ll N,px[MAXN],bx[MAXN];
inline ll qMul(ll a,ll b,ll p)
{
ll res=0;
while(b)
{
if(b&1) res=(res+a)%p;
a=(a+a)%p;b>>=1;
}
return res;
}
inline ll qPow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1) res=qMul(res,a,p);
a=qMul(a,a,p);b>>=1;
}
return res;
}
ll Exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return a;
}
ll gcd=Exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-a/b*x;
return gcd;
}
ll Excrt()
{
ll x,y,k;
ll M=bx[1],ans=px[1];
for(int i=2;i<=N;++i)
{
ll a=M,b=bx[i],c=(px[i]-ans%b+b)%b;
ll Gcd=Exgcd(a,b,x,y),Bg=b/Gcd;
if(c%Gcd!=0) return -1;
x=qMul(x,c/Gcd,Bg);
ans+=x*M;M*=Bg;ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
int main()
{
// freopen("excrt.in","r",stdin);
// freopen("excrt.out","w",stdout);
read(N);
for(int i=1;i<=N;++i) read(bx[i],px[i]);
write(Excrt());
return 0;
}
/*
3
11 6
25 9
33 17
*/

例题

NOI2018D2T1

在这道题中 $m_i$ 是固定的。

对于每一次选用的剑,我们可以用 multiset 预处理出来。

对于每条龙的恢复力 $p_i$ ,我们在砍完之后需要让龙的血量为 $p_i$ 的负 $k$ 倍。则在每次攻击的时候,我们需要满足 $atk_i\times x\ge a_i,atk_i\times x\equiv a_i\pmod{p_i}$ 。

这道题有一个特性,要么满足 $p_i=1$ ,要么满足 $a_i\le p_i$ 。所以需要分情况讨论。

对于满足特性 $1$ 的情况:

对于 $atk_i\times x\ge a_i$ 且 $p_i=1$ 时,只需求出将每只龙的生命值打到非正数的次数,取最大值即可,即 $\max(\frac{a_i}{atk_i})$ ,容易处理。

对于满足 $a_i\le p_i$ ,我们用 $\text{ExCrt}$ 来解:

同余式是 $atk_i\times x\equiv a_i\pmod{p_i}$ ,化成单式得到 $x\equiv a_i\times atk_i^{-1}\pmod{p_i}$ ,根据同余的消去律,我们先同时除以 $\gcd(atk_i,a_i,p_i)$ ,此时,如果 $atk_i,p_i$ 不互质,则无解;否则,转化完之后直接套板子求就完事了。

对于大数据 long long x long long 的情况,则会爆 $1e18$ ,所以使用龟速乘优化模数以免出错。也可以使用 long double 来存储,实现 $\mathcal O(1)$ 快速乘,但出错率较大。

1
2
3
4
5
6
typedef long long LoveLive;
inline LoveLive Multi(LoveLive x,LoveLive y,LoveLive Mod)
{
LoveLive tmp=(x*y-(LoveLive)((long double)x/mod*y+1.0e-8)*Mod);
return tmp<0?tmp+Mod:tmp;
}

此定义 typedef 源于 $\text{JK_Lover}$ 大帝。


BSGS

大步小步算法($\text{Baby Step,Giant Step}$),用于求解离散对数问题,求解同余方程 $a^x\equiv b\pmod p$ ,的解 $x$ ,其中 $a,p$ 互质。

记有 $m=\sqrt p$ ,对于任意的 $x$ ,将 $x$ 写成 $x=im-j(0\le j<m)$ ,则存在一个式子 $a^{i\times m}\equiv b\times a^j\pmod p$ ,则枚举 $j$ ,将 $b\times a^j$ 存到 $\text{hash}$ 表中,第二次枚举 $i$ ,在 $\text{hash}$ 表中查询与 $a^{i\times m}$ 相等的 $b\times a^j$ ,则一对 $i,j$ 确定一个解 $x$ 。如果求取最大或者最小解的话,则安排枚举顺序即可。

时间复杂度为 $\mathcal O(\sqrt p\times t)$ 。其中 $t$ 表示 $\text{hash}$ 表使用的时间。

对于最小解,我们首先使 $i$ 尽量小,然后使 $j$ 尽量大。因为有 $0\le j <m$ ,所以 $j$ 对答案的影响没有 $i$ 大。所以我们首先枚举 $a^{im}\equiv ba^j\pmod p$ ,对应出 $h[i]=j$ ,然后从小到大枚举 $i$ 找到与最小的 $i$ 对应的 $j$ ,就是最小解。

而对于 $a,p$ 互质的使用,则在于将 $a^{im-j}\equiv b\pmod p$ 转化为 $a^{im}\equiv b\times a^j\pmod p$ 时,使用了 $a^j$ 的逆元。

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ll A,B,P;
inline ll qPow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;b>>=1;
}
return res;
}
ll Bsgs(ll a,ll b,ll p)
{
std::map<ll,ll>Hash;Hash.clear();
b%=p;
ll t=std::sqrt(p)+1;
for(ll i=0;i<t;++i) Hash[b*qPow(a,i,p)%p]=i;
a=qPow(a,t,p);
if(!a) return b==0?1:-1;
for(ll i=1;i<=t;++i)
{
ll res=qPow(a,i,p);
int j=Hash.find(res)==Hash.end()?-1:Hash[res];
if(j>=0&&i*t-j>=0) return i*t-j;
}
return -1;
}
int main()
{
// freopen("bsgs.in","r",stdin);
// freopen("bsgs.out","w",stdout);
read(P,A,B);
ll ans=Bsgs(A,B,P);
if(ans==-1) puts("no solution");
else write(ans);
return 0;
}

EXBSGS

用于求解 $a,p$ 不一定互质的 $a^x\equiv b\pmod p$ 方程。

令 $d=\gcd(a,p)$ ,显然,在 $d=1$ 时,用 $\text{BSGS}$ 求解即可。

如果有 $d\not\mid b$ ,则有 $a^{x-1}\times\frac{a}{d}\equiv \frac{b}{d}\pmod {\frac{p}{d}}$ 重复该操作直到 $d=1$ ,得到 $a^{x-k}\times \frac{a}{\prod d}\equiv \frac{b}{\prod d}\pmod{\frac{p}{\prod d}}$ ,此时 $\gcd(a,\frac{p}{\prod d})=1$ ,转化成普通的 $\text{BSGS}$ 问题求解即可。

还需要判断 $x<k$ 的情况是否有解。此时也是可能有解的,直接枚举$x$ 从 $0\sim k$ ,暴力判断 $a^{x-k}$ 是否同余 $b$ 即可。

$k$ 是 $\mathcal O(\log p)$ 级的,所以时间复杂度是 $\mathcal O(\sqrt p)$ 。

模板题双倍经验

数据各有卡点,挺离谱的。

AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define gh() getchar()
#define re register
using namespace __gnu_pbds;
typedef long long ll;
gp_hash_table<ll,ll>Hash;
template<class T>
inline void read(T &x)
{
x=0;
char ch=gh(),t=0;
while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
template<class T>
inline void write(T x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
template<class T>
inline bool checkMax(T &x,T &y)
{
return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
return x>y?x=y,1:0;
}
ll A,B,P;
inline ll qPow(ll a,ll b,ll p)
{
ll res=1;
while(b)
{
if(b&1) res=res*a%p;
a=a*a%p;b>>=1;
}
return res;
}
ll Gcd(ll a,ll b)
{
return b==0?a:Gcd(b,a%b);
}
void Exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1,y=0;
return ;
}
Exgcd(b,a%b,x,y);
ll z=x;x=y;y=z-a/b*y;
}
inline ll Inv(ll a,ll b)
{
ll x,y;
Exgcd(a,b,x,y);
return (x%b+b)%b;
}
inline ll Bsgs(ll a,ll b,ll p)
{
Hash.clear();b%=p;
ll t=ceil(std::sqrt(p));
for(ll i=1;i<=t;++i)
{
b=b*a%p;Hash[b]=i;
}
ll tmp=qPow(a,t,p);b=1;
for(ll i=1;i<=t;++i)
{
b=b*tmp%p;
if(Hash[b]) return (i*t-Hash[b]+p)%p;
}
return -1;
}
inline ll ExBsgs(ll a,ll b,ll p)
{
if(b==1||p==1) return 0;
ll d=Gcd(a,p),k=0,Na=1;
while(d>1)
{
if(b%d!=0) return -1;
++k;b/=d;p/=d;Na=Na*(a/d)%p;
if(Na==b) return k;
d=Gcd(a,p);
}
ll f=Bsgs(a,b*Inv(Na,p)%p,p);
if(f==-1) return -1;
return f+k;
}
int main()
{
// freopen("exBSGS.in","r",stdin);
// freopen("exBSGS.out","w",stdout);
read(A,P,B);
while(A||B||P)
{
A%=P,B%=P;
ll ans=ExBsgs(A,B,P);
if(ans==-1) puts("No Solution");
else write(ans),puts("");
read(A,P,B);
}
return 0;
}
/*
5 58 33
2 4 3
0 0 0
*/

原根

定义一个 $g$ 满足 $g^1,g^2,g^3…g^{\phi(p)}$ 在模 $p$ 的意义下两两不相等,则 $g$ 是 $p$ 的原根。其中 $\phi(p)$ 表示与 $p$ 互质的数的个数。

对于一个质数 $p$ ,当 $g^i\not\equiv g^j\pmod p,i\ne j,i,j\in [0,p-1]$ 成立时, $g$ 是 $p$ 的原根。

原根存在条件

  • 奇质数一定存在原根;
  • 如果 $g$ 是 $p$ 的原根,则 $g+p$ 或 $g$ 是 $p^2$ 的原根。
  • 只有 $2,4,p^k,2\times p^k$ 的数存在原根,其中 $p$ 为奇质数,$k$ 为正整数。
  • 若 $p$ 存在原根,则 $p$ 的原根个数为 $\phi(\phi(p))$ 个。

查找原根

检验原根,则是枚举 $g$ 的质因数 $x$ ,并验证 $g^{\frac{\phi(p)}{x}}=1$ 是否成立,如果成立,则 $g$ 不是 $p$ 的原根。

因为有欧拉定理:$a^{\phi(p)}\equiv 1\pmod p$ ,所以如果上述式子提前成立,则证明其循环节不超过 $p-1$ ,则 $g$ 不是 $p$ 的原根。

经数学家证明,一个数如果存在原根,其最小原根是较小的,因此可以用枚举找原根。


对于两个数 $a,m\in\mathbb N_+$ ,有 $a\perp m$ ($a$ 与 $m$ 互质),使 $a^x\equiv 1\pmod m$ 成立的最小正整数 $x $ ,被称为 $a$ 模 $m$ 的,记作 $\operatorname{ord}_ma$ 。

阶的性质

  1. $a^n\equiv 1\pmod m$ 的充要条件是 $\operatorname{ord}_ma\mid n$ 。
  2. $\operatorname{ord}_ma\mid\varphi(m)$ 。
  3. 若 $a\equiv b\pmod m$ ,则 $\operatorname{ord}_ma=\operatorname{ord}_mb$ 。

二次剩余 - Cipolla

用于在模奇质数 $p$ 意义下开根号,即求方程 $x^2\equiv n\pmod p$ 的解 $x$ 。

勒让德符号

定义 $(\frac{n}{p})=n^{\frac{p-1}{2}}$ 称为勒让德符号

根据欧拉准则

  • 当 $(\frac{n}{p})\equiv 1\pmod p$ 时,$n$ 是 $p$ 的二次剩余,原方程有解;
  • 当 $(\frac{n}{p})\equiv -1\pmod p$ 时, $n$ 不是 $p$ 二次剩余,原方程无解;
  • 当 $(\frac{n}{p})\equiv 0\pmod p$ 时,$n\equiv 0\pmod p$ 。

求解二次剩余

对于 $n$ 是 $p$ 的二次剩余,我们随机值一个 $a$ ,使 $a^2-n$ 不为 $p$ 的二次剩余。(期望步数为 $2$ )记一个 $\omega=\sqrt{a^2-n}$ ,类似于复数的定义,定义一个新数域 $z=x+y\times\omega(x,y\in\mathbb N)$ ,可以得到 $x\equiv \pm(a+\omega)^{\frac{p+1}{2}}\pmod p$ 为原方程的解。


简单证明:(省略 $\pmod p$ 的书写)

由 $x\equiv \pm(a+\omega)^{\frac{p+1}{2}}$ 得到:$x^2\equiv(a+\omega)^p(a+\omega)$ ,由二项式定理展开得到:

$(a+\omega)^p\equiv\sum^p_{i=0}(^p_i)a^i\omega^{p-i}$

然后根据 $\text{Lucas}$ 定理得到当且仅当 $i=\{0,p\}$ 时, $(^p_i)$ 模 $p$ 不为 $0$ 。从而得到:

$(a+\omega)^p\equiv a^p+\omega^p$ 。又有 $a^p\equiv a$ ,则 $\omega^p\equiv \omega\times(\omega^2)^{\frac{p-1}{2}}\equiv-\omega$ 。

则:

$x^2\equiv (a-\omega)(a+\omega)\equiv a^2-\omega^2\equiv n$

证毕。


所谓使用的 $\text{Lucas}$ 定理,则是由 $\binom{p}{i}=\frac{p^{\underline{i}}}{i!}$ ,而 $\binom{p}{i}$ 在模 $p$ 意义下当且仅当 $i=\{0,p\}$ 成立时不为 $0$ 。

斐波那契数列循环

可以证明,在模 $p$ 意义下,斐波那契数列有循环节,且循环节长度上界是 $6p$ ,即在至多 $6p$ 的情况下,模 $p$ 的斐波那契会进入循环。

生日悖论与指针扫描

随机取出两个 $pos$ 并检验以 $pos$ 为起始的两位是否出现过。由生日悖论可以得到期望下,只要 $\mathcal O(\sqrt p)$ 次即可得到一个循环节,但不一定最小。然后枚举因数验证。

矩阵大步小步

对矩阵进行 $\text{BSGS}$ ,令转移矩阵为 $A$ ,则有 $A^k=I$ ,由斐波那契定义得到 $A$ 一定存在逆。

结论法

  • 当 $p$ 十分小的时候,可以直接开摆;
  • 若 $p$ 为奇质数:
    • 若 $5$ 是模 $p$ 意义下的二次剩余,循环节长度一定是 $p - 1$ 的约数;
    • 否则,循环节长度一定是 $2p + 2$ 的约数;
  • 否则, $p$ 是合数,也有结论,但不可用。