poj 1061 개구리 의 데이트 - 유클리드 확장 알고리즘

s 보 를 설정 한 후 두 개구리 가 만나면 다음 과 같은 등식 을 만족 시 켜 야 한다.
　　　　(x+m*s)-(y+n*s)=k*l(k=0,1,2....)
살짝 변형 시 키 기:
　　　　(n-m)*s+k*l=x-y
    n - m = a, k = b, x - y = d, 즉
　　　　a*s+b*l=c
사실은 유클리드 알고리즘 을 확장 하 는 것 입 니 다. - 부정 방정식 을 푸 는 것 입 니 다. 。 
상식 에 정수 해 가 존재 한다 면 두 개 구 리 는 만 날 수 있 고 그렇지 않 으 면 안 된다.
대 원 방정식 a * t + b * p = d, 우 리 는 t, p 를 요구 합 니 다.
분명히 c 는 gcd (a, b) 의 배수 일 것 이다. 그렇지 않 으 면 양쪽 을 동시에 gcd (a, b) 로 나 누 면 오른쪽 은 소수 가 되 고 비합법적 이다.
따라서 d / gcd (a, b) 는 반드시 정수 이다.
c=gcd(a,b);
그래서 우 리 는 유클리드 확장 원 리 를 통 해 구 해 야 한다. a * t0 + b * p0 =gcd(a,b);
t0 을 얻 은 후에 t0 * (d / c) 이 가장 작은 해 입 니 다.(gcd (a, b) * d / c = d 때문에)
즉 방정식: a * t0 *(d / c) + b * p0 * (d / c) = d; 그런데 t0 이 마이너스 일 수도 있어 요.
우 리 는 약간의 변 화 를 할 수 있다.
a * ( t0 *(d / c) + b*n) + b * (p0 * (d / c) – a*n) = d; (n 은 자연수)   (+a*b*n-a*b*n)
그래서 t = 
t0*(d/c)%b   ,while( t< 0 ){  t+= b;     }
그렇다면 어떻게 유클리드 확장 원 리 를 통 해 t0 을 구 합 니까?
바로 a * x + b * t = gcd (a, b) 와 같은 방정식 에 대해 a > b 를 가정 하면 두 가지 상황 이 있다.
상황 1. b = 0 이면 방정식 은 x = 1; y = 0 으로 해 제 됩 니 다.
상황 2 、 만약 ab! = 0,
  
a * x + b * y = gcd (a, b) 를 설정 합 니 다.  (1)
1. 그리고 유클리드 원리 에서 gcd 를 구 할 때 우 리 는 gcd (a, b) = gcd (b, a% b) 가 있다 는 것 을 알 고 있다.
그럼 지금 (1) 중의 a, b 를 b, a% b 로 교체 하여 얻 을 수 있 습 니 다.
    b * x0 + (a % b) * y0 = gcd( b, a % b);     (2)
연립 2 식,
a * x + b * y = b * x0 + (a % b) * y0
                     = b * x0 + (a – a / b * b) * y0               
                     = a * y0 + ( x0 – a / b * y0 ) * b
          그래서 x = y0, y = x0 – a / b * y0;
한편, y0, x0 은 y1, x1 을 통 해 구 해 야 한다. 즉, gcd 를 구 하 는 것 처럼 계속 돌아 가 마지막 a% b = = 0 까지
이때 의 x0 = 1; y = 0; (상황 1 에 해당)
 다음은 유클리드 확장 프로그램 입 니 다.

void extend_euild(__int64 a, __int64 b)
{
	if (b==0)
	{
		t=1;
		p=0;

	}
	else
	{
		extend_euild(b,a%b);
		__int64 tmp=t;
		t=p;
		p=tmp-a/b*p;
	}
}

다음은 ac 코드: 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
 __int64 gcdc(__int64 a,__int64 b){  
    if(b==0)  
        return a;   
        return gcdc(b,a%b);  
}  
__int64 t,p,c;
void extend_euild(__int64 a, __int64 b)
{
	if (b==0)
	{
		t=1;
		p=0;

	}
	else
	{
		extend_euild(b,a%b);
		__int64 tmp=t;
		t=p;
		p=tmp-a/b*p;
	}
}

int main()
{
	
	__int64 x,y,n,m,l;
	scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&m,&n,&l);
if (m==n){  
        cout<<"Impossible"<<endl;  
        return 0;  
    }  
	__int64 a=n-m;
	__int64 b=l;
	__int64 d=x-y; 
 	__int64 gcd=gcdc(a,b); 

	if (d%gcd)
	{
		printf("Impossible
");
		return 0;
	}
	 
 
        extend_euild( a, b );
        
        t*=  d/gcd ;
        while( t< 0 )
        {   
            t+= b; 
        }
        printf( "%I64d
", t%b );
	
	
	return 0;
	
}