poj1061-青蛙的约会

题意：两只蛤蟆分别在操场的x,y处，他们分别以m,n的速度向同一个方向跳，问最终他们是否可以相遇
     0.设出同余方程
     1.exgcd解决

 

//#include <bits/stdc++.h> #include <iostream> #define X 10005 #define inF 0x3f3f3f3f #define PI 3.141592653589793238462643383 #define IO ios::sync_with_stdio(false),cin.tie(0), cout.tie(0); #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; typedef long long ll; //typedef unsigned long long Ull; //2^64 const int maxn = (int)1e6 + 10; const int MOD = (int)1e9 + 7; const ll inf = 9223372036854775807; const int N = 47; ll primer[maxn]; ll a[maxn]; int ans[maxn], num[maxn]; void ex_gcd(ll a, ll b, ll &d, ll &x, ll &y) { if (!b) { x = 1; y = 0; d = a; } else { ex_gcd(b, a%b, d, y, x); y -= x * (a / b); }; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } ll lcm(ll a, ll b) { return b / gcd(a, b)*a; } ll inv_exgcd(ll a, ll m) { ll d, x, y;ex_gcd(a, m, d, x, y);return d == 1 ? (x + m) % m : -1; } ll inv1(ll b) { return b == 1 ? 1 : (MOD - MOD / b)*inv1(MOD%b) % MOD; } void e_gcd(ll a, ll m,ll &d,ll &x,ll &y) {if (!m) x = 1, y = 0, d = a;elsee_gcd(m, a%m, d, y, x),y -= a / m * x; } // a=m=0时是无解的 int main() {IO;ll x, y, n, m, l;cin >> x >> y >> m >> n >> l;ll a = m - n, b = y - x;if(a<0)a=-a,b=-b;if(!a){cout<<"Impossible"<<endl;return 0;}m = l;ll d,xx,yy;e_gcd(a,m,d,xx,yy);if (b%d!=0)cout<<"Impossible"<<endl;else{cout<<((xx*b/d)%(m/d) + m/d) % (m/d)<<endl;}return 0; }

 

总结

以上是生活随笔为你收集整理的poj1061-青蛙的约会的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。