> 先将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,
> 无解的判断,




LZ的算法有问题啊
当gcd(a,b)!=1时
(ax+by)%gcd(a,b)==0是吧?
那么(ax+by)肯定是gcd(a,b)的倍数,也就不等于1
所以这种情况下ax+by=1是无解的.

所以首先传入的a和b要保证他们互质
也就是先做这一步a=a/gcd(a,b);   b=b/gcd(a,b);
然后再传递参数.

然后最后计算通解的时候
应该是
对于不定方程ax+by=c的通解为：
x=x0*c+b*t
y=y0*c-a*t
(d=1所以消去了)

• Re:不清楚算法的可以进来, (325) atyuwen 2008-05-04 19:49:29