POJ 1061 青蛙的约会

~~~题目链接~~~

思路：设青蛙要跳x次才相遇， 可得方程 (a+xm)%L = (b+xn)%L 推出 x(m-n) + yL = b-a. 根据扩展欧几里德算法可求出一组x(m-n) + yL = gcd(m-n, L)的一组解， 当(b-a)为gcd(m-n, L)的倍数时原方程才有整数解， 现在要求求最小的跳动次数x， 思想参考了ComeOn4MyDream的~~资料~~

求最小的跳动次数x， 简单的说来就是通过通解 X = X1+K*L/gcd(m-n, L), 来求第一回大于0的数， 这个数是以L/gcd(m-n, L)为单位增加的。

code：

#include <stdio.h>void gcd(__int64 a, __int64 b, __int64 &d, __int64 &x, __int64 &y){    if(!b)    {        d = a;        x = 1;        y = 0;    }    else    {        gcd(b, a%b, d, y, x);        y -= x*(a/b);    }}int main(){    __int64  a = 0, b = 0, c = 0, d = 0, m = 0, n = 0, x = 0, y =0, L = 0, s1 = 0, s2 = 0, t = 0;    while(scanf("%I64d %I64d %I64d %I64d %I64d", &s1, &s2, &m, &n, &L) != EOF)    {        a = m-n, b = L, c = s2-s1;        if(a<0) a = -a, c = -c;        gcd(a, b, d, x, y);        if((c)%d)            printf("Impossible\n");        else        {            x *= (c)/d;           /* t = x/(b/d);            x -= t*(b/d);            if(x<0)                x += b/d;*/           t = b/d;           x = (x%t+t)%t;           printf("%I64d\n", x);        }    }    return 0;}

2楼ultimater昨天 09:58

c++里直接有GCD函数，可以简化代码。

Re: ulquiorra0cifer昨天 15:41

回复ultimatern我这个是扩展欧几里德函数， 原名extended_gcd， 求解线性方程，白书上的， c++中也有函数？

1楼ultimater昨天 20:27

可能有，哈哈；