 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
不清楚算法的可以进来,先将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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
