Poj1061 frog dating (extended Euclid)

Frog dating
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 146847 Accepted: 34169
Description

Two frogs met on the Internet , They had a good chat , So it's necessary to meet . They are happy to find that they live on the same latitude line , So they agreed to go west , Until we meet . But before they set out, they forgot a very important thing , I didn't ask about the other person's characteristics , There is no specific meeting place . But the frogs are optimistic , They think that as long as they keep jumping in a certain direction , Always meet each other . But unless the two frogs jump to the same point at the same time , Otherwise, we will never meet . To help these two optimistic frogs , You were asked to write a program to determine if the two frogs could meet , When will we meet .
We call these two frogs frogs A And frogs B, And set the latitude line east longitude 0 Degree is the origin , From east to West , Unit length 1 rice , In this way, we get a number axis with the head and tail connected . Set frogs A The starting point coordinates of are x, frog B The starting point coordinates of are y. frog A Can jump at a time m rice , frog B Can jump at a time n rice , It takes the same time for two frogs to jump once . The total length of the latitude line L rice . Now it's up to you to figure out how many times they jump before they meet .
Input

The input only includes one line 5 It's an integer x,y,m,n,L, among x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000.
Output

Output the number of jumps required to meet , Output a line if it's never possible to meet "Impossible"
Sample Input

1 2 3 4 5
Sample Output

4

The main idea of the topic ： There are two frogs with a circumference of L On the circle of x and y The position starts to jump to the left , The speed of the first frog is m, The speed of the second frog is n, Ask the two frogs if they can meet at the same time and place

Set two frogs in t Time to meet , be ： (x+mt)-(y+nt)=k*L(k = 0, 1, 2,…)
Transposition to ： (n-m)t+kL=x-y
Turn into Expand Euclid The template questions ax+by=n
Find whether there is an integer solution x

about ax+by=n：
1、 To calculate Gcd(a, b), if n Can not be Gcd(a, b) to be divisible by , Then the equation has no integer solution ; otherwise , Divide both sides of the equation by Gcd(a, b), A new indefinite equation is obtained a’ * x + b’ * y = n’, here Gcd(a’, b’)=1;
2、 Use Euclidean algorithm to solve the equation a’ * x + b’ * y = 1 A set of integer solutions x0, y0, be n’ * x0,n’ * y0 It's the equation a’ * x + b’ * y = n’ A set of integer solutions ;
3、 According to the related theorems in number theory , We can get the equation a’ * x + b’ * y = n’ All integer solutions of are ：
x = n’ * x0 + b’ * t
y = n’ * y0 - a’ * t
(t Integers )

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)// extended euclidean algorithm 
{
    
    if(b==0)
    {
    
        x=1;y=0;
        return a;  // Reach the recursive boundary and start to return to the upper layer 
    }
    ll r=exgcd(b,a%b,x,y);
    ll temp=y;    // hold x y Become the next layer 
    y=x-(a/b)*y;
    x=temp;
    return r;     // obtain a b Maximum common factor of 
}
int main() {
    
    ll x,y,m,n,l;
    cin >> x >> y >> m >> n >> l;
    // (x+m*s)-(y+n*s)=k*l -----> (n-m)*s+k*l=x-y  convert to a*x+b*y=c
    ll a = n-m,b=l,c=x-y,X,Y;
    ll r=exgcd(a,b,X,Y);
    if(c%r) {
    
        cout << "Impossible" << endl;
    }
    
    else {
    
        X=X*c/r;
        ll b2=b/r; // Why b2 How about mold taking ,x The general solution is x = n' * x0 + b' * t , When the b' After taking the mold ,x=n'*x0%b', here x Minimum 
        cout << (X%b2+b2)%b2 << endl;// Deal with negative numbers 
    }
    return 0;
}