Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:不清楚算法的可以进来,

Posted by xiaobo at 2009-03-15 22:14:04 on Problem 1061
In Reply To:不清楚算法的可以进来, Posted by:zhaokkk27 at 2007-09-20 13:59:12
> 先将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,
> 无解的判断,

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator