【OI之路】02数论算法-1公约数公倍数与欧几里得

2.1.0 前言:

%和mod都表示C++中的取余运算
$\lfloor x \rfloor$就是向下取整
数论这一章,建议大家用C++实现的时候以long long为主
长文预警!


2.1.1 取余和取模

顺便讲讲~
首先声明C++中的%运算符是取余运算
基本思路:①$c=a/b$ ②$r=a-c\times b$
取余:在①中,向0方向取整
取模:在①中,向负无穷方向取整
举个栗子:
(4)/(-3)≈-1.3
$4 rem (-3)=4-(-1)\times (-3)=1$
$4 mod (-3)=4-(-2)\times (-3)=-2$
C++中的%运算符其实是rem,但为了方便我比较习惯用mod表示,小心混淆
划重点:数论中为了化公式,经常要变成$r=a-\lfloor a/b \rfloor \times b$的形式


2.1.2 最大公约数Greatest Common Divisor

gcd(x,y)=x和y的最大公约数
公共约数中最大的
定义:gcd(x,0)=x
划重点:约数的定义域是自然数,所以不能是负数!

2.1.3 最小公倍数Least Common Multiple

lcm(x,y)=x和y的最小公倍数
公共倍数中最小的

2.1.4 补充知识

x*y=最小公倍数*最大公倍数
最小公倍数=x/最大公倍数*y (这样不容易爆)

证明:
设两个数为x和y,其最大公约数为a,则
最小公倍数为$(x/a)\times (y/a)\times a=x\times y/a$
最大公约数和最小公倍数的乘积为$(a)\times (x\times y/a)=x\times y$


2.1.5 欧几里得算法Euclid

又名辗转相除法,对于大小关系没有要求
内容:
$gcd(a,b)=gcd(b,a\%b)$
证明:

  1. 设d是a,b的一个约数,所以a/d,b/d为整数
  2. $r=a-k\times b 【0\leq r<b,k为整】$
    同时除以d,$r/d=a/d-kb/d$
    因为$a/d-k\times (b/d)$为整数
    所以r/d也是整数,所以r是d的倍数
  3. d本身就是a,b的约数,又d是r的约数,所以是a,b,a%b的公约数
    既然公约数是一样的(因为d并非定值,可以应用于所有公约数)
    最大公约数也必然相等,得证
    1
    2
    3
    4
    int Euclid(int a,int b)
    {
    return (b==0)?a:Euclid(b,a%b);
    }

时间复杂度:$O(log2b)$,证明


2.1.6 扩展欧几里德算法ExEuclid

内容:
利用 $gcd(a,b)=gcd(b,a\%b)$
递归求解 $ax+by=gcd(a,b)$ 【属于丢番图方程】
证明:

Ⅰ.

该方程必定是多解的,但我们只需要知道一个解,
就能得出其他解,下文为简洁设$GCD=gcd(a,b)=gcd(b,a\%b)$
$x=x0-b/GCD\times t$
$y=y0-a/GCD\times t$
注意上面两个通解公式只能选择其中一个,
然后获得另一个,其存在意义在于保证都是整数解
举个栗子:2x+3y=7,就是解2x+3y=1
$x_0=-1,y_0=1$
$x=(1-3y)/2,y=(1-2x)/3$
$x=x_0-b/GCD\times t=-1-3\times t$
$y=y_0-a/GCD\times t=1-2\times t$
t=1 x=-4则y=3
t=2 x=-7则y=5
原理(这东西网上根本没人说啊啊啊啊,只有乱引经据典自我搪塞的):
首先,这个t可以看作一个系数,那么对于同一个方程显然x的t增大(t)则y的t变小(-t)
带入:$a(x_0+b/GCD\times t)+b(y_0-a/GCD\times t)=GCD$
化简:$ax_0+by_0=GCD$
感觉很神hh

Ⅱ.

假设当前要求gcd(a,b),并求出了一组x和y使得$ax+by=GCD$
已经求出gcd(b,a%b)并求出了一组tx和ty使得$b\times tx+(a\%b)\times ty=GCD$
那么这两个相邻的状态之间是否存在某种关系呢?
$ax+by=GCD=b\times tx+(a\%b)\times ty$
$ax+by=b\times tx+(a-\lfloor{a/b}\rfloor \times b)\times ty$
$ax+by=b\times tx-\lfloor{a/b}\rfloor \times b\times ty+a\times ty$
$ax+by=b\times (tx-\lfloor{a/b}\rfloor \times ty)+a\times ty$
所以$x=ty,y=tx-\lfloor{a/b}\rfloor\times ty$
这个其实挺好推的,不推荐死记硬背
记住普通欧几里得后要用时再推一遍就好了

Ⅲ.

x转最小非负整数解:
$t=B/GCD$
$x=(x\%t+t)\%t$
举例:
初始:x=-1 y=1
2x+7y=5
t=B/GCD=7/1=7
最后:x=6 y=-1

Code

递归求解,用指针传递x,y

1
2
3
4
5
6
7
8
9
10
11
12
ll ExEuclid(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll tx,ty;
ll d=ExEuclid(b,a%b,tx,ty);
x=ty;y=tx-(a/b)*ty;
return d;
}

2.1.7 扩展欧几里德算法的运用1

解不定方程Ax+By=K(得到的x和y只是其中一组解)
给出A、B、K,求出x和y,满足Ax+By=K。

1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
ll A,B,K;scanf("%lld%lld%lld",&A,&B,&K);
ll x,y;
ll d=ExEuclid(A,B,x,y);
if(K%d!=0) printf("no solution!");
else
{
x=x*K/d;y=(K-A*x)/B;//保险~
printf("%lld %lld",x,y);
}
}

测试点:Caioj1153

2.1.8 扩展欧几里德算法的运用2

求解同余方程
已知a,b,m,求x的最小非负整数解,使得ax=b(mod m)
通俗讲就是ax mod m=b mod m
那么b是个常数,所以直接b=b%m,不影响结果

$ax\%m=b\%m$
$ax-\lfloor{ax/m}\rfloor \times m=b$
$ax+m\times (-\lfloor{ax/m}\rfloor )=b$
然后两边都有x怎么办?
直接当作x和y的某种关系即可,因为我们只要求x。

Ax+By=K
A=a,B=m,K=b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main()
{
ll a,b,m;scanf("%lld%lld%lld",&a,&b,&m);
ll A=a,B=m,K=b;
ll x,y;
ll d=ExEuclid(A,B,x,y);
if(K%d!=0) printf("no solution!");
else
{
x=x*K/d;
ll t=B/d;
ll XX=(x%t+t)%t;
printf("%lld",XX);
}
}

测试点:Caioj1154

2.1.9 扩展欧几里德算法的运用3

同余方程是这样的:已知a,b,n,求x的最小非负整数解,使得ax=b(mod m)
同余方程组是这样:也是求x的最小非负整数解,但已知a=1,b数组和m数组
x=b[1](mod m[1])
x=b[2](mod m[2])
x=b[3](mod m[3])
……………………
x=b[n](mod m[n])

在x=b(mod m)中,与上一个同理,由于b和m都是常数,可以令b=b%m
即x%m=b
将x当作P以防混淆,并新设x为商(即倍数)
$m\times x+b=P$

我们先选取前面两个柿子来寻找公共解:
$m1\times x+b1=P……①$
$m2\times y+b2=P……②$
①-② $m1\times x+(-m2)\times y=b2-b1$
A=m1,B=-m2,K=b2-b1
调用ExEuclid得到x

等等,不对!B居然是负数!根据前面公约数的描述,不能求负数!
网上无数人忽略了这个问题,反正我是没看到有人说这一句的
那怎么办?实现的时候,我们并不需要y(因为可以由x得出),那么就把B换做正数,求出一个-y
虽然这道题不用,但万一以后碰到这种情况而且还有求y,记得取相反数还原

$t=B/d$
$x=x\times K/d$
最小非负整数解$XX=(x\%t+t)\%t$

$P=m1\times XX+b1+若干倍的LCM(m1,m2)$
若干倍的LCM(m1,m2)是因为XX只是其中一个最小非负整数解,
仔细思考一下就会发现加上最后这个部分对于①和②都没有影响,x依然是整数
我们要求 同余方程组 的解,就要考虑周全

回归到 $x=m1\times XX+b1(\mod LCM(m1,m2))$
【提醒一下:因为是模,其实里面已经暗含“若干”了】
最早的格式 $x=b(\mod m)$

综上所述:
$b=m1\times XX+b1$
$m=LCM(m1,m2)$

如此合并,最后一个b就是答案
等到最后一次的时候,因为我们不再需要考虑后面了
将“若干”取0就是最小非负整数解了

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
int main()
{
int n;scanf("%d",&n);n--;
ll b1,m1;scanf("%lld%lld",&b1,&m1);b1=b1%m1;
ll XX;
while(n--)
{
ll b2,m2;scanf("%lld%lld",&b2,&m2);b2=b2%m2;
ll A=m1,B=m2,K=b2-b1;
ll x,y;
ll d=ExEuclid(A,B,x,y);
if(K%d!=0)
{
printf("no solution!");
return 0;
}
else
{
x=x*K/d;
ll t=B/d;XX=(x%t+t)%t;
b1=m1*XX+b1;
m1=A*B/d;//LCM(m1,m2)=LCM(A,B)
}
}
printf("%lld",b1);
}

测试点:
Caioj1155
Poj2891
(poj要调换输入、把无解换-1、多组数据)


2.1.10 总结一下

exgcd其实和gcd很像啦
把这些认认真真消化后,以后复习很快滴

顺带一提,目前网上介绍OI方面的扩展欧几里得的文章很少
所以到处综合网上文章加上个人思考写下本文,希望能对大家有所帮助!

2018.01.24 UP:
写这篇文章的时候我的博客还不支持公式,
大家将就着看吧,懒得改了,影响不是太大。

2018.03.28 UP:
咳咳,忍不住还是改好了……

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/7748.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%