Poj 1061 青蛙的约会(扩展欧几里得解线性同余式）

一、Description

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

Input

输入只包括一行5个整数x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

Output

输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

二、题目分析

这道题用到了扩展欧几里得算法解线性同余问题，小弟数论没怎么学。今天看到一篇精辟的题解，于是略作修改，引用之。原文请看http://blog.csdn.net/swordholy/article/details/4423543

根据题意可知，题目要求的是求(X + K * M)mod L=(Y + K * N)mod L这个模方程的k的最小整数解；跟据模的性质对这个方程变形得:K * ( M - N ) + T * L=Y--X( T为引进的一整数);

令A= (M - N) ; B = Y - X; 得：K * A + T * L =B ( 0)

看到这个式子是不是感觉很眼熟，对，它就是扩展欧几里得法能解的标准方程A * X + B * Y= D 的标准形；唯一的不同是扩展欧几里得D 是前面两系数A，B的最大公约数;而(0)式中的B就不能保证了。

1、不过没关系，先用扩展欧几里得得出K * A + T *L=gac(A,L) 的一个解k0,t0;再观察两个式子：

K * A + T * L =B ( 0)

K0 * A + T0 * L=D (1) (令D = gcd(A,L))

将(0)式两边都除以D，得：

K * （A / D）+ T * (L /D)=B/D

因为D为A,B的最大公约数，所以A / D,L / D为整数，所以B / D必定为整数，否则方程无解；

将(1)式两边都乘以B / D 与( 0 )式比较：

K * A + T * L =B ( 0)

K0 *( B / D) * A + T0 *( B / D)* L=B (1)

得K = K0 * B / D; T = T0 * B / D;

2、接下来就是由一个解扩展成一个解系：

( 1）除以D得： K0 * (A / D ) + T0 * ( L / D）=1

因为(A / D )和( L / D）互质，将方程写成：

(K0 + U * ( L / D）) * (A / D ) + ( T0 + V * (A / D ) ) * ( L / D）=1;

只要U * ( L / D） * (A / D ) + V * (A / D ) ) * ( L / D）=0成立就行；

所以K ，T 的解系可以写成 k = (K0 + U * ( L / D）) * (B / D ) ,T=( T0 + V * (A / D ) ) * ( B / D）

接下来就是求k的最小整数解了；

因为K = (K0 mod (L / D) + (U + K0 / ( L / D) ) * ( L / D)) * (B / D);

所以Kmin=(K0 * (B / D)) mod (L / D);

3、大功基本高成了，还差最后一步，那就是如何用扩展欧几里得解K * A + T * L=gac(A,L)

对A * X + T * L = D;

           递归调用时令A = B ; B = A % B;(辗转相除法,求最大公约数)

           将其变为形式（2） B * X + A % B * Y = D;

                           变形:B * X + A * Y - (A / B) * B * Y = D;

再变:A * Y+ B ( X - A / B * Y)=D; (3)

与(2）式B * X + A % B * Y = D;比较:

得：

当A = B ; B = A % B时：X = Y ; Y = X - A / B * Y;调用过程中的X , Y 就是对应的A , B 的解；当回到顶层时，A , B 就是最初的A ，B,所以此时的X，Y就是所求解。

三、Java代码

import java.util.Scanner; 

public class Main { 

    static long x0, y0; 

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        long x = scan.nextInt();

        long y = scan.nextInt();

        long m = scan.nextInt();

        long n = scan.nextInt();

        long L = scan.nextInt();

        if (x > y) {

            long t = y;

            y = x;

            x = t;

            t = n;

            n = m;

            m = t;

        }

        long a = Math.abs(m - n);

        long b = L;

        long c;

        if (m > n) {

            c = y - x;

        } else {

            c = x - y + L;

        } 

        long d = gcd(a , b);

        if(c%d!=0){

            System.out.println("Impossible");

        }else{

            long add1 = x0*c/d ;

            long add2 = Math.abs(b/d);

            while( add1 <0 ){

                add1 += add2;

            }

            while(add1 - add2 >= 0){

               add1 -= add2;

            }

            System.out.println(add1);

        }

    }

    public static long gcd(long a, long b) {

        long t, d;

        if (b == 0) {

            x0 = 1;

            y0 = 0;

            return a;

        }

        d = gcd(b, a % b);

        t = x0;

        x0 = y0;

        y0 = t - a / b * y0;

        return d;

    }

  }

秒客网

Poj 1061 青蛙的约会(扩展欧几里得解线性同余式）

相关文章