首页 > 代码库 > POJ1061 青蛙的约会
POJ1061 青蛙的约会
1 /* 2 POJ1061 青蛙的约会 3 http://poj.org/problem?id=1061 4 扩展欧几里得 5 6 原题为求t使得,存在l满足 7 (x+mt)-(y+nt)=cl 8 即求 9 cl+(n-m)t=x-y 10 * 11 * 12 * 13 */ 14 15 #include <cstdio> 16 #include <cmath> 17 using namespace std; 18 long long ex_gcd(long long a,long long b,long long &x,long long &y)//solve x,y in a*x+b*y=ex_gcd(a,b,x,y)=gcd(a,b); 19 { 20 if(b==0LL) 21 { 22 x=1LL; 23 y=0LL; 24 return a; 25 } 26 long long ans=ex_gcd(b,a%b,x,y); 27 long long tmp=x; 28 x=y; 29 y=tmp-a/b*y; 30 return ans; 31 //x = x0 + (b/gcd)*t 32 //y = y0 – (a/gcd)*t 33 34 } 35 int main() 36 { 37 long long x,y,m,n,l; 38 scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l); 39 long long a=l,b=n-m; 40 l=x-y; 41 long long xx,yy; 42 long long gcd=ex_gcd(a,b,xx,yy); 43 if(l%gcd) 44 { 45 printf("Impossible\n"); 46 return 0; 47 } 48 49 long long r=l/gcd; 50 //while(xx<=0) 51 //{ 52 //xx=xx+b/gcd; 53 //yy=yy-a/gcd; 54 //} 55 yy=yy*r; 56 a=a/gcd; 57 long long t=yy%a; 58 while(t<0) 59 t+=a; 60 printf("%lld\n",t); 61 return 0; 62 }
POJ1061 青蛙的约会
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。