首页 > 代码库 > AC日记——青蛙的约会 poj 1061
AC日记——青蛙的约会 poj 1061
青蛙的约会
POJ - 1061思路：
扩展欧几里得；
设青蛙们要跳k步，我们可以得出式子
m*k+a≡n*k+b(mod l)
式子变形得到
m*k+a-n*k-b=t*l
(m-n)*k-t*l=b-a
然后，exgcd函数求出k
然后输出刚刚大于0的k即可
来，上代码：
#include <cmath>#include <cstdio>#include <cstring>#include <iostream>using namespace std;long long n,m,a1,b1,l,xx,yy;long long exgcd(long long a,long long b,long long &x,long long &y){ if(b==0) { x=1,y=0; return a; } long long r=exgcd(b,a%b,x,y),tmp=x; x=y,y=tmp-a/b*y; return r;}int main(){ scanf("%lld%lld%lld%lld%lld",&a1,&b1,&m,&n,&l); long long a=m-n,b=l,c=b1-a1; if(a<0) a=-a,c=-c; long long r=exgcd(a,b,xx,yy); if(c/r*r==c) { xx=xx*c/r,l=l/r; if(xx>0) xx=xx%l; else xx=xx%l+l; cout<<xx; } else cout<<"Impossible"; return 0;}
AC日记——青蛙的约会 poj 1061
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。