> 先将2个青蛙调整到A左B右,
> 
> 这道题的实质是解不定方程ax+by=c,
> 其中,
> a=|m-n| (i.e. 2个青蛙步长差)
> b=L     (i.e. 圈长)
> c=y-x   (i.e. A比B跳的快,即m>n) 或者 
> c=x-y+L (i.e. A比B跳的慢,即m<n)
> 
> 解这个不定方程可以用扩展欧几里德算法,
> 下面简单说明下这个算法,
> ////////////////////////////////////////////////////////////////////
> int Euclid_Extended(int a,int b,int &x0,int &y0)  
> {  
>      int t,d;  
>      if (b==0) {
>         x0=1; y0=0;
>         return a;
>      }
>      d=Euclid_Extended(b,a%b,x0,y0);  
>      t=x0;  
>      x0=y0;  
>      y0=t-a/b*y0;  
>      return d; 
> }
> 
> 函数返回值为gcd(a,b),并顺带解出ax+by=1的一个解x0,y0,
> 
> 对于不定方程ax+by=c的通解为：
> x=x0*c/d+b/d*t
> y=y0*c/d+a/d*t
> 
> 当c%gcd(a,b)!=0时,不定方程无解.
> ////////////////////////////////////////////////////////////////////
> 
> 剩下需要做的就是用x=x0*n/d+b/d*t
> 求出一个最小的正整数x,这步就很简单了。
> 
> 需要注意以下几点:
> 类型开到long long,
> 无解的判断,

• Re:不清楚算法的可以进来, (2) 55 2008-03-04 15:07:20
• Re:不清楚算法的可以进来, (2) 55 2008-03-04 15:07:21