首页 > 代码库 > extended_gcd(扩展欧几里德算法) 青蛙的约会
extended_gcd(扩展欧几里德算法) 青蛙的约会
#include <stdio.h>#include <math.h>long long gcd(long long x,long long y){ if(y==0) { return x; } return gcd(y,x%y);}void extended_gcd(long long a,long long b,long long &x,long long &y){ long long t; if(b==0) { x = 1; y = 0; return; } extended_gcd(b,a%b,x,y); t=x; x = y; y = t- a/b*y; return;}int main( ){ long long x, y, m, n, l; long long a,b,c,d,p,q; long long t; while(scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l)!= EOF ) { a= n-m; b=l; c= x-y; d= gcd(a,b); if(c%d!=0) { puts( "Impossible" ); continue; } a/= d,b/= d,c/= d; extended_gcd(a,b,p,q); p*= c; t= p%b; while(t<0) { t+= b; } printf("%lld\n",t); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。