扩展欧几里德 POJ 1061

欧几里德的是来求最大公约数的，扩展欧几里德，基于欧几里德实现了一种扩展，是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理，证明是用裴蜀定理)，关于欧几里德的证明请看上篇。

基本算法:基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设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，所以递归可以结束。

所以求代码可以如下

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a; // a,b的最大公约数的求法(gcd) 
    }
    int r = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return r;//最大公约数 
}

POJ 1061青蛙的约会这个题是求不定方程的解的，有题意可列方程(n-m)*s + k * L = x - y; 、

令a = n - m; b = L; c = x - y;

这个式子这时就是a * s + b * k = c;典型的不定方程

求解过程：

1. 首先计算gcd(a, b); 如果c不能整除gcd(a, b)那么就是没有解的，因为gcd(a, b)是a*s+b*k的线性组合的最小正整数, x,y∈z; 否则，方程两边同时除以gcd(a, b)得到新的方程a' * s + b' * k = c'; 这时候a', b'是互质的，所以gcd(a', b') = 1。

2. 利用上面所说的欧几里德算法求出方程a' * s + b' * k = 1的一组整数解x0,y0, 那么c' * x0, c' * y0就是方程a' * s + b' * k = c' 的一组整数解

3. 求方程组的通解，这时候就需要一些数论中的证明(a' * s + b' * k = c' 可以写成 a' * (s + t * b') + b' * (k - t * a') = c'， t为整数，所以通解s_通=s + t * b', k_通= k - t * a')

通解为：s_通=s + t * b', k_通= k - t * a'

所以它的最小正整数解为 (t % b' + b') % b';

代码如下：

#include <cstdio>
#include <iostream>

typedef long long LL;

int gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    LL t = x;
    x = y;
    y = t - (a / b) * y;
}
int main()
{
    
    LL x, y, n, m, L;
    while (~scanf("%I64d %I64d %I64d %I64d %I64d", &x, &y, &m, &n, &L))
    {
        LL a, b, c, r, k1, k2, GCD;
        a = n - m;
        b = L;
        c = x - y;
        GCD = gcd(a, b);
        if (c % GCD != 0)
        {
            puts("Impossible");
        }
        else
        {
            a /= GCD;
            b /= GCD;
            c /= GCD;
            exgcd(a, b, k1, k2);
            k1 *= c;//为其中一个解 
            k1 = (k1 % b + b) % b;//最小正整数解 
            printf("%I64d\n", k1);
        }
    } 
    return 0;
}

扩展欧几里德 POJ 1061

推荐阅读