简介扩展欧几里德定理

欧几里德定理:

对于整数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的大小，如果ab,那么a%b

事实发现证明gcd(a, b)==gcd(b, a%b)==d这个式子会缩小处理的数据的范围；

欧几里德应用：

用来求a，b的最大公约数。

代码实现：

int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,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
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 %lldn", x, y);
        }
        else
            printf("-1n");
    }
    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;
}

但这只是求得了一组解x1，y1

对于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

拓展GCD，如何由一组解推出多组解？

—————————-分割线———————————————-

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”

样例输入

1 2 3 4 5

样例输出

4

解析

设两只青蛙跳了t步，A的坐标为x+mt,B的坐标为y+nt，他们相遇的时候满足x+mt-(y+nt) = pL(p表示两青蛙走过的路程相差p圈)
移项后：(n-m)t+Lp=x-y

#include 
#include 
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;
}

http://icpc.upc.edu.cn/problem.php?cid=2592&pid=2

题目描述

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)

样例输入

2
7 3
7 4

样例输出

Case #1: 5/2
Case #2: 2

提示

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)，其中一个为负数，而且题目中必须 by – ax == 1.公式得出来的可能是 -1.

得不出答案，书中写到有多组解，解等于 x+ka’ , y-kb’ (a’ = a / gcd(a,b) , b’ = b / gcd(a,b) ，k为整数).

但是， 只有a>0才不符合情况,a只能每次减b。

#include 
#include 
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;
}