poj 1061 青蛙的约会（扩展欧几里得）

2019-04-14 19:08发布

站内文章 / 模拟电子
15109 0 1182
http://poj.org/problem?id=1061
思路：设它们跳了t次相遇，那么有 (x+t*m)-(y+t*n) = z*l(z是一个整数，表示它们路程差是l的z倍)，变形得 (n-m)*t + z*l = (x-y); 令 a = n-m; b = l; c = x-y; 那么原式变为 a*t + z*b = c;
扩展欧几里得模板，求解形如a*x + b*y = gcd(a,b)方程。 LL extend_gcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1; y = 0; return a; } LL d = extend_gcd(b,a%b,x,y); LL t = x; x = y; y = t-a/b*y; return d; }
方程a*x + b*y = c有解的前提是 gcd(a,b) | c,在这个基础上方程有d=gcd(a,b)个不同的解。其中基础解x0 = x'*(c/d)%b(其中x'为a*x'+b*y' = gcd(a,b)的解)；通解为xi = x0 + i * (b/d)。 #include #include #include #include #include #include #include #include #include #include #include #define LL long long #define _LL __int64 #define eps 1e-8 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 10; LL extend_gcd(LL a, LL b, LL &x, LL &y) { if(b == 0) { x = 1; y = 0; return a; } LL d = extend_gcd(b,a%b,x,y); LL t = x; x = y; y = t-a/b*y; return d; } int main() { LL x,y,m,n,l; LL a,b,c,d; while(~scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&l)) { a = n-m; b = l; c = x-y; LL t,z; d = extend_gcd(a,b,t,z); if(c%d != 0) { printf("Impossible "); continue; } t = t*(c/d); t = (t%b+b)%b; printf("%lld ",t); } return 0; }

热门文章