一篇文章讲明白gcd,exgcd,lct,exlct

0,取模与整除

这一部分讨论在c++中取模与整除的特性

取模操作,又称取余,在C++中的符号是\%,和乘除法属于同一运算优先级,模数不允许出现零
正数模正数结果是非负数,很好理解,但出现了负数怎么办?

#include <iostream>
using namespace std;
int main() {
cout << 8 % 3 << endl;
cout << 8 % -3 << endl;
cout << -8 % 3 << endl;
cout << -8 % -3 << endl;
return 0;
}
/*
2
2
-2
-2
*/

结论:取模的结果只与被模数的正负号有关

整除操作,是做除法后舍去余数得到的整数结果,依然需要讨论,出现了负数怎么办?

#include <iostream>
using namespace std;
int main() {
cout << 8 / 3 << endl;
cout << 8 / -3 << endl;
cout << -8 / 3 << endl;
cout << -8 / -3 << endl;
return 0;
}
/*
2
-2
-2
2
*/

结论:整除的结果和被除数与除数是否同号有关,商的绝对值必然等于绝对值之商,还有一个特性,就是商*除数+余数=被除数

进行整除运算时不要使用floor(),ceil()等容易导致浮点误差的函数.

一些常用的小技巧:

//向上取整(仅适用于正数)
int ceil_div(int a,int b){
return (a+b-1)/b;
}
//要求结果为正的取模
int mod_postive(int a,int b){
if(b<0)a=-a,b=-b;
return (a%b+b)%b;
}

1,gcd(Greatest Common Division),最大公约数

使用辗转相除法(或称Euclid算法)计算

int gcd(int a,int b){
return b?a:gcd(b,a%b);
}

使用这种写法无需额外讨论正负号,a与b的大小的问题,但若a,b符号不同,计算出的结果正负号也难以寻找规律,不过显然有abs(gcd(a,b))=gcd(abs(a),abs(b))

没有必要讨论a,b中包含0的情况

辗转相除法的时间复杂度是O(log n),显然,每递归一次,max(a,b)至少减小一半,不过笔者认为这个上界还是太粗糙.

2,exgcd(Extend Grestest Common Division,扩展gcd)

定理:

若gcd(a,b)=g,则必然存在x,y,使得ax+by=g

辗转相除法的过程本身就是这个定理的构造性证明,因此要求得x,y,只需要保留在运算过程中被舍弃的信息

int exgcd(int a,int b,int &x, int &y){
if(!b){
x=1;
y=0;
return a;
}
ans=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return ans;
}

注意,解(x,y)不是唯一的,实际上有无穷多组,因为若(x,y)是一组解,(x+kb/g,y-ka/g)也是一组解,上述算法计算出的是x,y绝对值分别小于b/g,a/g的解的其中一组.

如果这时候a,b,x均大于0,g=1,那么a,x就互为模b意义下的逆元

因为不可避免地会出现负数(实际上a,b,x,y至少一个为负数),因此许多exgcd题目中正负号的讨论都会让人自闭,比如青蛙的约会,此时是降低思维难度,减少分类讨论情况数的最好方法是先透彻地理解题意,确定哪个参数有符号的限制;然后抓住辗转相除法的本质,对特解做出正确的恒等变换.

3,crt(Chinese Remain Theory,中国剩余定理)

中国剩余定理得名于中国古代的这样一个题目

有东西不知道多少个,三个三个数剩两个,五个五个数剩三个,七个七个数剩五个,问这堆东西有多少个

即,求同余方程组

x%3=2
x%5=3
x%7=5

显然解不是唯一的,因为若a满足条件,a+k(3*5*7)必定满足条件

求解这类问题就需要使用中国剩余定理

回过头来看前面的同余方程组,要求解x,只需要找到(y1,y2,y3),使得

y1%3=1 　　y1%5=0 　　y1%7=0
y2%3=0　　 y2%5=1　　 y2%7=0
y3%3=0　　 y3%5=0 　　y3%7=1

于是很显然地,x=2*y1+3*y2+5*y3,于是问题就变成了怎么求解(y1,y2,y3)

我们用符号rev(a,b)来表示a(或者a\%b)在取模b意义下的逆元,这个值容易通过对a,b做exgcd求得

那么便有了

y1=rev(5*7,3)*5*7
y2=rev(3*7,5)*3*7
y3=rev(3*5,7)*3*5

需要注意的是,模数必须两两互质,否则rev(a,b)未必存在,上述方法失效.

4,excrt(Extand Chinese Remain Theory,扩展中国剩余定理)

如果模数不互质,同余方程组未必有解,比如模3余1,模9却余8.但未必无解,比如模3,6,9都得到2.那么对于这种情况如何求解,或者证明无解呢?将同余方程组写成如下的形式

x%m1=a1
x%m2=a2
x%m3=a3
......
将同余方程依次两两合并,比如第一个和第二个式子:
x%m1=a1
　　　　　　==> x%lcm(m1,m2)=a'
x%m2=a2
接下来的任务就是求解这个a',求解的过程实际上是在求解同余方程组的如下等价形式
x%m1=a1 <==> x=a1+y1m1
x%m2=a2 <==> x=a2+y2m2
联立
m1y1-m2y2=a2-a1
调用exgcd函数求解
g=exgcd(m1,m2,y1',y2')
如果g不是a2-a1的因数,输出无解,否则
y1=(a2-a1)/g*y1'
y2=(a2-a1)/g*y2'
所以能够得到等式
x=(a1+(m1/g)(a2-a1)y1)+y'*lcm(m1,m2)
记a'=a1+(m1/g)(a2-a1)y1,那么我们完成了前两个式子的合并过程,得到x%lcm(m1,m2)=a',如果一直到所有式子都被合并且未出现无解的情况,最后得到的a'就是特解,a'+lcm(m1,m2....)就是通解

5,龟速乘

在计算excrt的时候可能会出现两个乘数和模数都在long long范围内,但是没取模的积却溢出的尴尬情况,为了防止溢出或误差,应当用类似快速幂的方式求解整数乘法

LL turtle_mult(LL base,LL n,LL mod){
if(n<0){
base=-base;
n=-n;
}
LL ans=0;
while(n){
if(n&1)ans=(ans+base)%mod;
base=base+base%mod;
n>>=1;
}
return ans;
}

注意,龟速乘不允许用于计数的那个乘数为负,所以一开始要特判一下