hello kity
期待您的批阅,由于写解题报告时 不一定考虑的很周到,所以如果您有什么不懂的地方,请您留言,然而一天之内我肯定会看见您信息,再对代码注释详细,让您更好的阅读
分类
最新评论
最新留言
链接
RSS
计数器
223071
功能
POJ(1061 青蛙的约会 扩展欧几里德求解不定方程)
spoiler
posted @ 2011年5月06日 16:15
in 数论
, 6912 阅读
题目大意:
Description
两只青蛙在网上相识了,它 们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很 重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除 非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么 时候碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的 数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。 现在要你求出它们跳了几次以后才会碰面。
我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的 数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。 现在要你求出它们跳了几次以后才会碰面。
Input
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
题目分析:首先青蛙A B 相遇必须满足:( x+ m*s ) - ( n*s + y ) = k*L; 这里 s 代表他们跳的步数,k代表他们在第几圈 相遇!
这里如果你想尝试枚举的话,只能说这里的浮动性太大了,谁能确定 s 的范围呢,又有谁知道 最小的 s 是多大呢,这个也许
会很大的!所以只能 用 扩展的欧几里德 求这个不定方程!
会很大的!所以只能 用 扩展的欧几里德 求这个不定方程!
求解 不定方程: ( x+ m*s ) - ( n*s + y ) = k*L 首先我们把这个方程变形 : s * ( n - m) + k* L = x -y ; 注意观察这个方程, 这就是所谓的线性同余方程, 对于这种方程,如果有解 必须满足 (x - y)% gcd ( n-m, L )==0 不然就无解, 输出Imposible!
这里通过看别人的总结 与自己看书,介绍一下怎么用欧几里德扩展求不定方程:
设标准方程式为: a*x +b*y =d (a,b已知)
第一步:
首先求出gcd(a,b) ,然后化简方程,使得a/=gcd(a,b); b/=gcd(a,b); d/=gcd(a,b);
这样的话化简过后的 a,b就是互质的啦!(下面说的a,b 都是已经化简过的 注意哦 不再声明了)
第二步:
先求出 a*x+b*y=gcd(a,b) 的一组特解,也就是方程 a*x+b*y=1 的一个特解 (a,b互质 所以最大公约数为1!)
然后将特解(x0, y0) 代入方程,并变形: a* x0 *d + b* y0 *d= d 再仔细看看, (x=x0*n ,y=y0*n) 这不是
第一步里面 化简后的标准方程的一组解麽?然后我已经求得 标准方程的一组解了,继续讨论 解系里面的最小值吧!
第一步里面 化简后的标准方程的一组解麽?然后我已经求得 标准方程的一组解了,继续讨论 解系里面的最小值吧!
第三步:
根据解系的 公式: x =x1 + b* t ; y =y1 - a *t; 我们首先假设他最小的解x=0 ,然后求出 此时的 t=-x1/b; 然后带入
求最小的解x=x1+b*t=x1 - b*t ;因为此时的t为 负数, 减去他的 负数,就是等于加上他!
代码+部分注释:
#include<iostream> #include<cmath> #include<cstdio> using namespace std; long long gcd(long long a,long long b){ long long c; if(a<b){ c=a; a=b; b=c; } while(b){ c=b; b=a%b; a=c; } return a; } long long extended_gcd(long long a,long long b,long long &x,long long &y){ long long ans,t; if(b==0){ x=1; y=0; return a; } else{ ans=extended_gcd(b,a%b,x,y); t=x; x=y; y=t-(a/b)*y; } return ans; } int main(){ long long x,y,m,n,l; long long a,b,d,k,s,t; while(scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l)!=EOF){ a=n-m; b=l; d=x-y; long long r=gcd(a,b); if(d%r!=0){ printf("Impossible\n"); continue; } a/=r; b/=r; d/=r; extended_gcd(a,b,s,k); s=s*d; k=k*d; t=s/b; s=s-t*b; if(s<0) s+=b; printf("%lld\n",s); } return 0; }
2011年5月06日 16:43
第一次深入点的学习数论,以后继续下去,加油!每个知识块都大量练习!给自己加油!
2011年6月06日 02:05
你能帮我解释下这里吗?
if(s<0)
s+=b;
2011年6月12日 15:18
如果s小于0 这里就不是合法解了 然后要加上一个b 让他变成最小的正解 呵呵
2013年4月21日 01:47
代码应该还可以简化,你解释的字让我不容易看清,建议改种颜色。
2013年8月12日 05:56
你这个答案基本上正确,但是有些数据有问题,比如:
x=3, y=1, m=2, n=1, L=4
你的答案是-6,正确答案应该是2。
而且其实不用long long,int就够用了。
2013年8月12日 06:08
如果t=s/b是正值的话,你这个就没问题,如果是负值就错了,应该是t=static_cast<int>(floor(static_cast<double>(s)/b));
2013年8月12日 06:13
好像还是不对……
2013年8月12日 06:20
找到问题了,你gcd算出来的r和extended_gcd算出来的r不一样,一个是-1,一个是+1。你从一开始就用extended_gcd算出来的r就好了。
2013年8月12日 06:28
囧……好象还是不对……
2013年8月12日 15:00
这下终于明白了,你这t是反着的,所以应该用t=static_cast<int>(ceil(static_cast<double>(s)/b));