poj1061-青蛙的约会（扩展欧几里德算法）

一，题意：

　　　两个青蛙在赤道上跳跃，走环路。起始位置分别为x，y。
　　　每次跳跃距离分别为m，n。赤道长度为L。两青蛙跳跃方向与次数相同的情况下，
　　　问两青蛙是否有方法跳跃到同一点。输出最少跳跃次数。
二，思路：
　　本题用到扩展欧几里德算法求二元一次不定式方程(ax+by=c)。
　　1,化简方程，然后求解 ax+by = gcd(a,b);
　　2,求解 ax+by = c;
　　3,求出最小非负整数解x1
三，步骤：
　　1,设青蛙跳了s步。
　　　则有方程 (x + m*s) - (y + n*s) = l*k --> (n - m)*s + l*k = x - y
　　　令 a = n - m , b = l , x' = s , y' = k , c = x - y ; d = gcd(a,b);
　　　所以方程化为 a*x' + b*y' = c ;
　　2,先利用扩展欧几里德算法求解方程 a*x' + b*y' = gcd(a,b);
　　3,利用方程 a*x' + b*y' = gcd(a,b) 的解 x0 以及公式 x = x0*c/d 求出 a*x' + b*y' = c 的解 x1 ; 前提是：d|c ( c 能被 d 整除 );
　　4,利用周期性变化求最小的非负整数解公式: x1 = ( x1%(b/d) + (b/d) ) % (b/d);
　　　若方程的a*x' + b*y' = c的一组整数解为(x1,y1)，则它的任意整数解为 ( x1 + k* ( b/d ) , y1 - k*( a/d ) ) ( k 取任意整数 ) , T = b/d 就为 x1 增长的周期
　　　　i，若x1为负值，取最大的非正值：x1 = x1 % T ;若x1为正值，以下两步无影响。
　　　　ii，取正， x1 = x1 + T ;

　　　　iii，防止 i中的x1=0 即 ii中的x1 = T ,那么 x1 = x1 % T ;

 #include<iostream>

 using namespace std ;

 //扩展欧几里德算法 : 用来求解  a*x+b*y=gcd(a,b) 方程x,y可能的值

 void exgcd(long long a,long long b,long long& d,long long& x,long long& y){  //int& a  表示传入a的地址

     if(!b){d=a;x=;y=;}                   // d用来存储gcd(a,b)的值

     else {exgcd(b,a%b,d,y,x);y-=x*(a/b);}

 }

 int main(){

     long long minx,x,y,m,n,l,d,x1,y1,T;

     cin>>x>>y>>m>>n>>l;

     exgcd(n-m,l,d,x1,y1);  //(n-m)*s+l*k = gcd(n-m,l) ==> x1=s y1=k;

     if((x-y)%d!=) cout<<"Impossible\n";  //方程有解的条件是：x-y 能被 gcd(n-m,l) 整除

     else{

         x1=x1*((x-y)/d);   //思路2中方程 a*x1 + b*y1 = c 的解 x1 ;

         T=l/d;           //x的增长周期 T

            x1=(x1%T+T)%T;//求出最小非负整数解

         cout<<x1<<endl;

     }

     return ;

 }

秒客网

poj1061-青蛙的约会（扩展欧几里德算法）

相关文章