博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj_1061_青蛙的约会
阅读量:5301 次
发布时间:2019-06-14

本文共 1112 字,大约阅读时间需要 3 分钟。

分析:如果两只青蛙能够相遇,则满足: (x+mt)-(y+nt)=p*L;  t为跳的次数 则:x-y+(m-n)*t=p*L;  即:(m-n)≡(y-x)mod L 此线性同余方程有解当且仅当 gcd(m-n,L)|(y-x) 利用欧几里德求解ax+by=c即可,其中a=m-n,b=L,c=y-x 求出一个特解后,令d=gcd(a,b) 特解为:x0=c/d*x0 方程的所有解公式为x=(d/d*x0+L/d*i)(i=0,1,2,……,d-1) 最小解为(x0mod(L/d)+L/d)mod(L/d);
View Code
#include 
typedef __int64 LL;LL extgcd(LL a,LL b,LL &x,LL &y){ if(!b) { x = 1; y = 0; return a; } LL g = extgcd(b,a%b,x,y); LL t = x; x = y; y = t - (a / b) * y; return g;}inline LL _abs(__int64 x){ return x > 0 ? x : -x;}bool modeq(LL a,LL c,LL m,LL &x){ LL g,y; g = extgcd(a,m,x,y); if( c%g ) return false; else { x = (c/g * x) % m; x %= _abs(m/g); if(x<0) x += _abs(m/g); return true; }}int main(){ LL x,y,m,n,L; LL A,C,M,X0; while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF) { A = m-n; C = y-x; M = L; if(modeq(A,C,M,X0)) printf("%I64d\n",X0); else printf("Impossible\n"); } return 0;}

转载于:https://www.cnblogs.com/pcoda/archive/2012/05/09/2492480.html

你可能感兴趣的文章
研磨JavaScript系列(五):奇妙的对象
查看>>
面试题2
查看>>
selenium+java iframe定位
查看>>
P2P综述
查看>>
第五章 如何使用Burp Target
查看>>
Sprint阶段测试评分总结
查看>>
sqlite3经常使用命令&amp;语法
查看>>
linux下编译openjdk8
查看>>
【python】--迭代器生成器装饰器
查看>>
Pow(x, n)
查看>>
安卓当中的线程和每秒刷一次
查看>>
每日一库:Modernizr.js,es5-shim.js,es5-safe.js
查看>>
ajax连接服务器框架
查看>>
wpf样式绑定 行为绑定 事件关联 路由事件实例
查看>>
利用maven管理项目之POM文件配置
查看>>
TCL:表格(xls)中写入数据
查看>>
Oracle事务
查看>>
String类中的equals方法总结(转载)
查看>>
属性动画
查看>>
标识符
查看>>