POJ 1061 AC代码

两只青蛙A，B在一条纬度上，纬度线总长为L，A在x处，B在y处。他们同时朝西走，A每次能走m，B每次能走n。问这两只瓜皮青蛙是否有可能相遇，如果不能相遇输出”Impossible”，如果能相遇则输出跳跃的次数。

思路

这题虽然是个数论基础题，但是恶心了我零零碎碎快一天的时间…到最后POJ还挂了交不上去。先记录一下大体的思路吧。之后再补代码。

首先，建模过程还是非常愉悦的：
设跳了t次相遇，此时A蛙所在的位置为 (x+nt)%L，B蛙所在位置为 (y+mt)%L
AB相遇即 )modL
他们相减一定是纬度线长度的整数倍，设为k*L
即 )t+kL=y−x
设a = m-n, b = L, c = y-x， 化为ax+by=c问题
令d = gcd(a, b, x, y)
如果d % c != 0 无解，否则有解

exgcd：
扩展欧几里得算法，简称 exgcd，一般用来求解不定方程，求解线性同余方程，求解模的逆元等
引理：存在 x , y 使得 gcd(a,b)=ax+by
证明：
当 b = 0 时，gcd(a,b) = a，此时 x = 1 , y = 0
当 b != 0 时，
设 ax1 + by1 = gcd(a,b) = gcd(b,a%b) = bx2 + (a%b)y2
又a%b = a - [floor(a/b)] * b
//特意这么写是因为我居然被这个公式卡了很久
则 ax1 + by1 = bx2 + ( a - a/b * b )y2
ax1 + by1 = bx2 + ay2 - a/b * by2
ax1 + by1 = ay2 + bx2 - b * a/b * y2
ax1 + by1 = ay2 + b( x2 - a/b * y2 )
根据恒等定理解得 x1=y2 , y1=x2-a/b*y2
因为当 b=0 时存在 x , y 为最后一组解
而每一组的解可根据后一组得到
所以第一组的解 x , y 必然存在
得证
　　
根据上面的证明，在实现的时候采用递归做法
先递归进入下一层，等到到达最后一层即 b=0 时就返回x=1 , y=0
再根据 x=y’ , y=x’-a/b/y’ ( x’ 与 y’ 为下一层的 x 与 y ) 得到当层的解
不断算出当层的解并返回，最终返回至第一层，得到原解
参考：欧几里德与扩展欧几里德算法
欧几里得算法与扩展欧几里得算法_C++
exgcd题集：扩展欧几里得专题

exgcd 模板

int exgcd(int a, int b, int& x, int& y){
    int d = a;
    if( b != 0 ){
        d = exgcd(b, a%b, y, x);
        y -= (a / b)*x；
    }
    else{
        x = 1; y = 0;
    }
    return d;
}

剩下的就是套个线性同余板子求解最小正整数解即为所求的 t

关于这道题目的缜密证明：POJ1061 青蛙的约会
关于这道题目的具体分析：POJ 1061青蛙的约会题解

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long ll;

ll exgcd( ll a, ll b, ll& x, ll& y ){
    if( b == 0 ){
        x = 1;
        y = 0;
        return a;
    }
    ll r = exgcd(b, a%b, x, y);
    ll t = x;
    x = y;
    y = t - a/b*y;
    return r;
}

int main()
{
    ll a, b, c, xx, yy, m, n, l;
    scanf("%lld%lld%lld%lld%lld",&xx, &yy, &m, &n, &l);
    // 设次数为t, 模常数k
    // (m-n)t + kl = y-x
    //  at+bk = c
    a = m - n;
    b = l;
    c = yy - xx;
    if( a < 0 ){
        a = -a;
        c = -c;
    }
    ll x, y;
    ll d = exgcd(a, b, x, y);
    if( c % d != 0 )
        puts("Impossible");
    else{
        x=x*(c/d)%b;
        x=(x%(b/d)+(b/d))%(b/d);
        printf("%lld
", x);
    }
    return 0;
}