简介扩展欧几里德定理
欧几里德定理:¶
对于整数a,b来说，gcd(a, b)==gcd(b, a%b)==d(a与b的最大公约数)，又称为辗转相除法
证明：
因为a是d的倍数，b是d的倍数；所以a%d=0； b%d=0；
设k=a/b；r=a%b；则 a=k*b+r；
由上得出：r=a-k*b；
因为a和b都是d的倍数，所以(a-k*b)也是d的倍数，所以r也是d的倍数；
所以gcd(a, b)==gcd(b, a%b)==d
而为什么要证明gcd(a, b)==gcd(b, a%b)==d这个式子成立呢？
其实证明gcd(a, b)==gcd(a, a%b)==d这个式子成立也是可以的，因为a也是d的倍数，但是在进行递归之前要进行一步操作，就是判断a与b的大小，如果a<b,就没办法进行递归或者循环求最大公约数，那么如果a
事实发现证明gcd(a, b)==gcd(b, a%b)==d这个式子会缩小处理的数据的范围；
欧几里德应用：
用来求a，b的最大公约数。
代码实现：
扩展欧几里德定律：¶
对于不完全为0的非负整数a，b;gcd(a, b)表示a, b的最大公约数，必定存在整数对x，y，满足a*x+b*y==gcd(a, b);
证明：
a*x1+b*y1=gcd(a, b);
b*x2+(a%b)*y2=gcd(b, a%b);
因为由欧几里德定理知：gcd(a, b)==gcd(b, a%b)
所以a*x1+b*y1=b*x2+(a%b)*y2; 因为r=a%b, r =a-k*b所以==>
a*x1+b*y1=b*x2+(a-k*b)*y2; 因为k=a/b;所以 ==>
a*x1+b*y1=b*x2+(a-(a/b)*b)*y2; 展开得到 ==>
a*x1+b*y1=b*x2+a*y2-b*(a/b)*y2; 转换得到 ==>
a*x1+b*y1=a*y2+b*(x2-(a/b)*y2);
观察上式可知 x1=y2, y1=x2-a/b*y2;
由此可知x1，y1是由x2，y2得出来的，由此类推x2，y2是由x3，y3得出来的，
那什么时候是终止呢？也就是递归gcd(a, b)中b=0时；也就是说此时a的值就是要求得最大公约数
即gcd(a, 0)此时由扩展欧几里得定律a*x+b*y==gcd(a, b)知 a*x+b*y=a;
解出x=1, y=0;
此时就是递归终止的地方：
扩展欧几里德应用：
就我目前所知的就是：求解不定方程；如a*x+b*y=c; 已知a, b, c的值求x和y的值
那么问题来了，如何将扩展欧几里德定律应用在求解不定方程呢？
可以这样转化 a*x+b*y=gcd(a, b)*c/gcd(a, b);
最后转化为 a*x/(c/gcd(a, b))+b*y/(c/gcd(a, b))=gcd(a, b); 最后求出的解x0，y0乘上c/gcd(a, b)就是最终的结果了
x1=x0*c/gcd(a, b);
y1=y0*c/gcd(a, b);
代码实现： 举例说明：http://codeforces.com/problemset/problem/7/C
#include<stdio.h>
long long exgcd(long long a, long long b, long long &x, long long &y);
int main()
{
long long a, b, c, ans, x, y;
while(scanf("%lld%lld%lld", &a, &b, &c)!=EOF)
{
ans=exgcd(a, b, x, y);
if(c%ans==0)
{
x=-x*c/ans;
y=-y*c/ans;
printf("%lld %lld\n", x, y);
}
else
printf("-1\n");
}
return 0;
}
long long exgcd(long long a, long long b, long long &x, long long &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
long long r=exgcd(b, a%b, x, y), t;
t=x;
x=y;
y=t-(a/b)*y;
return r;
}
对于x,y对应的解集是：
x=x1+b/gcd(a, b)*t;
y=y1-b/gcd(a, b)*t;
证明：
a*x+b*y=d,d=gcd(a,b).
推导：a*x1+b*y1=a*x2+b*y2
---->a*(x1-x2)=b*(y2-y1)
---->a/d*(x1-x2)=b/d*(y2-y1)
---->a/d,b/d互质
---->x1-x2=k*(b/d),y2-y1=k*(a/d)
----->x=x0+b/d*k,y=y0-a/d*k,k为任意整数。
参考于：
欧几里德和扩展欧几里德详解 以及例题CodeForces 7C
----------------------------分割线----------------------------------------------
http://icpc.upc.edu.cn/problem.php?cid=1437&pid=5
题目描述¶
两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
输入¶
输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
输出¶
输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"
样例输入¶
样例输出¶
解析¶
设两只青蛙跳了t步，A的坐标为x+mt,B的坐标为y+nt，他们相遇的时候满足x+mt-(y+nt) = pL(p表示两青蛙走过的路程相差p圈) 移项后：(n-m)t+Lp=x-y
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll d = exgcd(b, a%b, x, y);
ll t = x;
x = y;
y = t-(a/b)*y;
return d;
}
int main()
{
ll x,y,m,n,l;
cin>>x>>y>>m>>n>>l;
if(m==n)
{
cout<<"Impossible"<<endl;
return 0;
}
ll x1=0,y1=0,a=n-m,b=l,c=x-y;
ll d=exgcd(a,b,x1,y1);
if(c%d!=0)
{
cout<<"Impossible"<<endl;
return 0;
}
else
{
x1=x1*c/d;
x1=(x1%(b/d)+(b/d))%(b/d);
cout<<x1<<endl;
}
return 0;
}
题目描述¶
DIDIDI often takes a shower in school public bathroom. DIDIDI must take a shower in B days after the previous one, or he will die. For routine maintenance, bathroom closes one day per A days. But DIDIDI is lazy, he hopes he can take a shower as less as possible. So he wants to find a stable period for arranging dates of shower. For example, DIDIDI should take a shower every 3-day, and bathroom closes every Sunday. In order to minimize the shower times, in every two-week, DIDIDI can choose Monday, Thursday, Saturday (to avoid Sunday), Tuesday, Friday to take shower. In this case, he need to take a shower 2.5 times per week. Your assignment is to calculate how many times per A days DIDIDI need to take a shower.
输入¶
The first line of input contains a positive integer T telling you there are T test cases followed. Each test case will contain two integer, A, B.
输出¶
For each test case, print a line “Case #x: y”, where x is the case number (starting from 1) and y is times per A days of taking a shower. (if y is not a integer, please print fraction like “a/b”, gcd(a,b) = 1)
样例输入¶
样例输出¶
提示¶
Tips:1≤T≤2000,2≤A,B≤1e8 Case 1: if bathroom closes in 7th day every 7 days, he can take a shower in 1st,4th, 6th, 2nd,5th,1st, 4th, 6th, 2nd,5th …… every period contains five shower times and two 7-day, so answer is 5/2. Csse 2: if bathroom closes in 7th day every 7 days, he can take a shower in 3rd,6th, 3rd, 6th ……every period contains two shower times and a 7-day, so answer is 2.
解决¶
扩展欧几里得算法：a*x+b *y=gcd(a,b)
对于这个题，gcd==1的时候才会用到这个来求x,y。 但是得出的只有其中一个(x,y)，其中一个为负数，而且题目中必须 b*y - a*x == 1.公式得出来的可能是 -1.
得不出答案，书中写到有多组解，解等于 x+ka' , y-kb' (a' = a / gcd(a,b) , b' = b / gcd(a,b) ，k为整数).
但是， 只有a>0才不符合情况,a只能每次减b。
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e9+7;
ll gcd(ll a,ll b)
{
if(b==0)
return a;
else
return gcd(b,a%b);
}
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
ll d = exgcd(b, a%b, x, y);
ll t = x;
x = y;
y = t-(a/b)*y;
return d;
}
int main()
{
int t;
scanf("%d",&t);
for(int t1=1;t1<=t;t1++)
{
ll a,b;
scanf("%lld%lld",&a,&b);
ll g=gcd(a,b);
if(g==1)
{
ll x=0,y=0;
ll d=exgcd(a,b,x,y);
if(abs(a*x)-abs(b*y)<0)
{
x=abs(x);
y=abs(y);
if(x==1)
cout<<"Case #"<<t1<<": "<<y<<endl;
else
cout<<"Case #"<<t1<<": "<<y<<"/"<<x<<endl;
}
else
{
while(abs(a*x)-abs(b*y)>=0)
{
x=x-b/d;
y=y+a/d;
}
x=abs(x);
y=abs(y);
if(x==1)
cout<<"Case #"<<t1<<": "<<y<<endl;
else
cout<<"Case #"<<t1<<": "<<y<<"/"<<x<<endl;
}
}
else
{
if(b==g)
{
cout<<"Case #"<<t1<<": "<<a/g<<endl;
}
else
{
cout<<"Case #"<<t1<<": "<<a/g<<"/"<<b/g<<endl;
}
}
}
return 0;
}