首页 > 代码库 > 【poj 1061】青蛙的约会（数论--同余方程 拓展欧几里德）
【poj 1061】青蛙的约会（数论--同余方程 拓展欧几里德）
题意：已知2只青蛙的起始位置 a,b 和跳跃一次的距离 m,n，现在它们沿着一条长度为 l 的纬线（圈）向相同方向跳跃。问它们何时能相遇？（好有聊的青蛙 (??????‵) *）永不相遇就输出"Impossible"。（蠢得可怜 -_-!）
解法：用拓展欧几里德求同余方程的最小正整数解。(a+mx)-(b+nx)=k*l (k表示圈数) → (m-n)x=k*l+b-a → (m-n)x=b-a(mod l)。当然其实=(b-a)%l 更准确，但反正都是模，也没有关系啦。于是就像上题一样求了。
P.S.代码中有一处加了%p，和没加，时间差别还挺大的......但上一题又不怕......*(￣_￣)*
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 using namespace std; 6 #define N 2000000000 7 typedef long long LL; 8 9 LL mabs(LL x) {return x>0?x:-x;}10 LL exgcd(LL a,LL b,LL& x,LL& y)11 {12 if (!b) {x=1,y=0; return a;}13 LL tx,ty,d;14 d=exgcd(b,a%b,tx,ty);15 x=ty,y=tx-(a/b)*ty;16 return d;17 }18 int main()19 {20 LL aa,bb,m,n,l;21 scanf("%I64d%I64d%I64d%I64d%I64d",&aa,&bb,&m,&n,&l);22 LL a,b,c,x,y,p;23 a=m-n,b=l,c=bb-aa,p=l;24 LL d=exgcd(a,b,x,y);25 if (c%d!=0) printf("Impossible\n");26 else27 {28 x=(x*(c/d))%p;//厉害了！删了%p，就从0ms变到16ms了29 LL t=mabs(b/d);30 x=(x%t+t)%t;31 printf("%I64d\n",x);32 }33 return 0;34 }
【poj 1061】青蛙的约会（数论--同余方程 拓展欧几里德）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。