扩展欧几里德定理
对于不完全为
0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整
0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整
数对 x，y ，使得 gcd（a，b）=ax+by
#include<stdio.h>
int x,y,q;
void extend_Eulid(int a,int b)
{
if(b == 0)
{
x = 1;y = 0;q = a;
}
else
{
//printf("AA: %d BB: %d\n",a,b);
extend_Eulid(b,a%b);
int temp = x;
x = y;
y = temp - a/b*y;
//printf("A: %d B: %d X: %d Y:%d\n",a,b,x,y);
}
}
int main()
{
int a,b;
while(~scanf("%d%d",&a,&b))
{
extend_Eulid(a,b);
printf("%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b);
}
return 0;
}
求解 x，y的方法的理解
设 a>b。
1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；
2，ab!=0 时
设 ax1+by1=gcd(a,b);
bx2+(a mod b)y2=gcd(b,a mod b);
根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);
则:ax1+by1=bx2+(a mod b)y2;
即:ax1+by1=bx2+(a-[a/b]*b)y2=ay2+bx2-(a/b)*by2;
根据恒等定理得：x1=y2; y1=x2-[a/b]*y2;
这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。
使用扩展欧几里德算法解决不定方程的办法
对于不定整数方程pa+qb=c，若 c mod Gcd(a, b)=0,则该方程存在整数解，否则不存在整数解。
上面已经列出找一个整数解的方法，在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后， /*p * a+q * b = Gcd(a, b)的其他整数解满足：
p = p0 + b/Gcd(a, b) * t
q = q0 - a/Gcd(a, b) * t(其中t为任意整数)
至于pa+qb=c的整数解，只需将p * a+q * b = Gcd(a, b)的每个解乘上 c/Gcd(a, b) 即可
在找到p * a+q * b = Gcd(a, b)的一组解p0,q0后，应该是
得到p * a+q * b = c的一组解p1 = p0*(c/Gcd(a,b)),q1 = q0*(c/Gcd(a,b))，p * a+q * b = c的其他整数解满足：
p = p1 + b/Gcd(a, b) * t
q = q1 - a/Gcd(a, b) * t(其中t为任意整数)
p 、q就是p * a+q * b = c的所有整数解。
运用扩展欧几里德算法的题目：
简单的扩展欧几里德应用
#include<stdio.h>
#include<iostream>
int x,y,p;
void extend_Eulid(int a,int b)
{
if(b==0)
{
x=1;
y=0;
p=a;
}
else
{
extend_Eulid(b,a%b);
int temp;
temp=x;
x=y;
y=temp-a/b*y;
}
}
int main()
{
int a,b,i;
while(~scanf("%d%d",&a,&b))
{
extend_Eulid(a,b);
if(p!=1)
printf("sorry\n");
else
{
while(x<0)
{
x=x+b;
y=y-a;
}
printf("%d %d\n",x,y);
}
}
return 0;
}
n=A%9973，则n=A-A/9973*9973。又A/B=x，则A=Bx。所以Bx-A/9973*9973=n。令y=A/9973，即Bx-9973y=n；
只要能够求出x的值，就能得出(A/B)%9973的值，即x%9973；
利用扩展欧几里德算法可求出gcd(B,9973)=Bx1+9973y1=1的x1，等式两边同乘以n，得B(nx1)-9973(-ny1)=n。可知nx1就是Bx-9973y=n的解，即x=nx1。
若x的值求出来是负数，要先转化为正数
#include<stdio.h>
#include<iostream>
void exgcd(int a,int b,__int64 &x,__int64 &y)
{
if(b==0)
{
x=1;
y=0;
}
else
{
exgcd(b,a%b,x,y);
int temp;
temp=x;
x=y;
y=temp-a/b*y;
}
}
int main()
{
int m;
__int64 x,y;
__int64 n,b;
scanf("%d",&m);
while(m--)
{
scanf("%I64d%I64d",&n,&b);
exgcd(b,9973,x,y);
while(x<0)
x+=9973;
x*=n;
printf("%d\n",x%9973);
}
return 0;
}
另一种方法
思路：设A = k * 9973 + n ,A/ B = C, C = P * 9973 + x,x即为我们所求的答案。易知，A = k* 9973 + n =B * P * 9973
+ B * x,化简后得k * 9973 = B * P * 9973 + B * x - n，因此(B * x - n)%9973 = 0,n的值知道，B的值知道，又因为x的取值范围是0到9972，因此枚举x的值即可
+ B * x,化简后得k * 9973 = B * P * 9973 + B * x - n，因此(B * x - n)%9973 = 0,n的值知道，B的值知道，又因为x的取值范围是0到9972，因此枚举x的值即可
#include<stdio.h>
#define M 9973
int main()
{
int i,scase;
__int64 n,b;
scanf("%d",&scase);
while(scase--)
{
scanf("%I64d%I64d",&n,&b);
for(i=0;i<M;i++)
{
if((b*i-n)%M==0)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}
思路：假设青蛙跳的次数是k，当（x+k*m）%L=（y+k*n）%L成立时，能够碰面
即（x+k*m）-（y+k*n）=L*p（p是未知数），可得出不定方程k（n-m）+L*p=x-y，当（x-y）%gcd（k，L）=0时，两只青蛙可以碰面，
根据扩展欧几里德算法解决不定方程的方法即可求出k
#include<stdio.h>
__int64 q; //最大共约数
void exgcd(__int64 a,__int64 b,__int64 &k,__int64 &p)
{
if(b==0)
{
k=1;
p=0;
q=a;
}
else
{
exgcd(b,a%b,k,p);
__int64 temp=k;
k=p;
p=temp-a/b*p;
}
}
int main()
{
__int64 x,y,m,n,l,k,p;
while(~scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l))
{
exgcd(n-m,l,k,p);
// printf("%d %d\n",x1,y1);
if((x-y)%q==0)
{
k*=(x-y)/q;
k=(k%(l/q)+l/q)%(l/q);//当k为负数的时候转化为正数
printf("%I64d\n",k);
}
else
{
printf("Impossible\n");
}
}
return 0;
}
#include<stdio.h>
__int64 q; //最大共约数
void exgcd(__int64 a,__int64 b,__int64 &x,__int64 &y)
{
if(b==0)
{
x=1;
y=0;
q=a;
}
else
{
exgcd(b,a%b,x,y);
__int64 temp=x;
x=y;
y=temp-a/b*y;
}
}
int main()
{
__int64 x,y,a,b,c,k,p,m=1;
while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k))
{
if(a==0&&b==0&&c==0&&k==0) break;
p=1LL<<k;//k在移位时必须写为1LL<<k，否则因为移位默认按int操作，会出现问题
exgcd(c,p,x,y);
if((b-a)%q==0)
{
x*=(b-a)/q;
x=(x%(p/q)+p/q)%(p/q);//当x为负数的时候转化为正数
printf("%I64d\n",x);
}
else
{
printf("FOREVER\n");
}
}
return 0;
}
分别求出最小正整数x时的|x|+|y|和最小正整数y时|x|+|y|，然后输出最小|x|+|y|时的|x|和|y|；
#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;
int q; //最大共约数
void exgcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
q=a;
}
else
{
exgcd(b,a%b,x,y);
int temp;
temp=x;
x=y;
y=temp-a/b*y;
}
}
int main()
{
int x,y,a,b,c,x1,y1,x2,y2,max1,max2;
while(~scanf("%d%d%d",&a,&b,&c))
{
if(a==0&&b==0&&c==0) break;
exgcd(a,b,x,y);
x*=c/q;
y*=c/q;
x1=(x%(b/q)+(b/q))%(b/q);
y1=(c-a*x1)/b;
max1=abs(x1)+abs(y1);
y2=(y%(a/q)+(a/q))%(a/q);
x2=(c-b*y2)/a;
max1=abs(x2)+abs(y2);
if(max1<max2)
printf("%d %d\n",abs(x1),abs(y1));
else
printf("%d %d\n",abs(x2),abs(y2));
}
return 0;
}