重拾拓展欧几里得 & 简单不定方程

重拾拓展欧几里得 & 简单不定方程

过一段时间不用拓展欧几里得就把代码忘了，这是没有深入理解的恶果啊。写下一文，回忆回忆基础而重要的拓展欧几里得

拓展欧几里得函数 ex_gcd() 可以用于求解逆元，不定方程，同余式（随便也能把模与被模数的最大公约数求出来）。

贴上代码：

void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){ if(b==0){ d=a; x=1; y=0; return ; } ex_gcd(b,a%b,d,x,y); LL t=x; x=y; y=t-a/b*y;}

工作原理：

例如：number=225 mod=21

辗转相减：

225-21*10=15

21-15*1=6

15-6*2=3

6-3*2=0

最大公约数即是： 3

求解225模21的逆元：

当ex_gcd()递归终止时，两个数字的最大公约数被找到，两个数字化简后进行下面的回溯运算：

X是上一次的Y，Y是上一次的X减去(a/b)和上一次Y的乘积。

得到的x就是相关逆元（两个数字互质时的逆元）

75*3=225%7=1

中间值：

18435915192532888 225 21

18435915192532888 21 15

18435915192532888 15 6

18435915192532888 6 3

18435915192532888 3 0

3 0 1 6 3

3 1 -2 15 6

3 -2 3 21 15

3 3 -32 225 21

Process returned 0 (0x0)   execution time : 0.391 s

Press any key to continue.

关于实验的代码：

void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){ cout<

ex_gcd()在求解逆元和方面就不说了，下面聊一聊它在不定方程上的应用：

关于不定方程：

当然，实际写程序中更方便的做法是： 在用拓展欧几里得时直接带入x0,y0就行，最后X0=c/d*x0   Y0=c/d*y0

相关例题：

The Balance

​​ 求出x和y的绝对值，且|x|+|y| min，|ax|+|by| min

分析：利用ex_gcd()求得一组解x0,y0，得出通解的表达式：x=x0-Bt    y=y0+At

|x|+|y|=|x0-Bt|+|y0+At|

将最开始的a,b设成a

小负大正

|x0-Bt|是一个凹函数（t<0 and t>=0）

|y0+At| 是一个增函数

且因为B=b/d   A=a/d  所以较小的速度大于增大的速率。所以整体是一个凹函数。而那个凹点就是使得x0-Bt=0的t值。求出它并在其周围几个点枚举一下就能得到答案。（距离设为2能AC，但是设为1就不行了  T_T）

#include #include using namespace std;typedef long long LL;void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){ if(b==0){ d=a; x=1; y=0; return ; } ex_gcd(b,a%b,d,x,y); LL t=x; x=y; y=t-a/b*y;}LL abs(LL a){ return a<0?-a:a;}int main(){ //freopen("cin.txt","r",stdin); LL a,b,c; while(~scanf("%lld%lld%lld",&a,&b,&c)){ if(a==0&&b==0&&c==0) break; bool sp=0; if(a>b){ sp=1; a=a^b; b=a^b; a=a^b; } LL d,x0,y0; ex_gcd(a,b,d,x0,y0); x0=x0*(c/d); y0=y0*(c/d); LL t=x0*d/b,Min=0x3f3f3f3f,Min2=0x3f3f3f3f; LL ans1,ans2; for(int i=t-2;iget){ ans1=x0-b/d*i; ans2=y0+a/d*i; Min=get; Min2=a*ans1+b*ans2; } else if(Min==get){ LL all=abs(a*(x0-b/d*i))+abs(b*(y0+a/d*i)); if(all

SGU 106 The equation

​​[y1,y2]内解的个数。

相关知识：

拓展欧几里的求解不定方程：ax+by=c 假设x1<=x2,  y1<=y2

当a=0，b=0时，如果c=0 解的个数是：（x2-x1+1)(y2-y1+1) ; 如果c!=0，解的个数是0

当 a=0 ， b!=0时，如果c%b=0，且-c/ b在y的要求范围内，那么解的个数是x2-x1+1 ;  如果c%b! = 0，或 -c/b不 在y的要求范围内，那么解的个数是0

当 a! =0，b =0时 过程类似。

当a!=0,b!=0,进入不定方程的解决程序：

方程转化成 ax+by=-c

拓展欧几里的a,b参数是正整数，所以将其进行相应的设置。

if(a<0)  [x1,x2] --> [-x2,x1]

if(b<0)  [y1,y2] --> [-y2,y1]

分开讨论：

x1, y1 确定下界

x2, y2 确定上界

图变成这个样子了：

所以，这样确定上下界：

#include #include #include using namespace std;typedef long long LL;void ex_gcd(LL a,LL b,LL &d,LL &x,LL &y){ if(b==0){ d=a; x=1; y=0; return ; } ex_gcd(b,a%b,d,x,y); LL temp=x; x=y; y=temp-a/b*y;}int main(){ //freopen("cin.txt","r",stdin); LL a,b,c; LL x1,x2,y1,y2; while(~scanf("%lld%lld%lld",&a,&b,&c)){ scanf("%lld%lld",&x1,&x2); scanf("%lld%lld",&y1,&y2); if(b==0){ if(a!=0){ if(c%a==0&&(-c/a)<=x2&&(-c/a)>=x1) { //one x but name y printf("%lld\n",y2-y1+1); } else puts("0"); } else { LL ans=(x2-x1+1LL)*(y2-y1+1); if(c==0)printf("%lld\n",ans); else puts("0"); } } else if(a==0){ if(b!=0){ if(c%b==0&&(-c/b)<=y2&&(-c/b)>=y1) { //one y but many x printf("%lld\n",x2-x1+1); } else puts("0"); } else { LL ans=(y2-y1+1LL)*(x2-x1+1); if(c==0)printf("%lld\n",ans); else puts("0"); } } else { c=-c; if(c<0){ c=-c; a=-a; b=-b; } if(a<0) { a=-a; LL t=x1; x1=-x2; x2=-t; } if(b<0) { b=-b; LL t=y1; y1=-y2; y2=-t; } LL d,x,y; ex_gcd(a,b,d,x,y); if(c%d){ puts("0"); continue; } a/=d; b/=d; c/=d; x=x*c; y=y*c; LL l=max(ceil((y-y2)*1.0/a),ceil((x1-x)*1.0/b)); LL r=min(floor((y-y1)*1.0/a),floor((x2-x)*1.0/b)); if(r

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。