POj 1061カエルのデート

拡張ユークリッド:
拡張ユークリッドを用いて,不定方程式を解いた.例えば、p*a+q*b=c<1>の不定方程式(a,b,cが既知)については、拡張ユークリッドアルゴリズムで解くことができる.<1>式については、解があれば、必ず以下のものがある.
gcd(a,b)/c = 0;
      
拡張ユークリッドアルゴリズムを用いて不定方程式を解決する方法
不定整数方程式pa+qb=cの場合、c mod Gcd(a,b)=0の場合、その方程式には整数解が存在し、そうでなければ整数解は存在しない.
p*a+q*b=Gcd(a,b)の解p 0,q 0のセットが見つかった後、p*a+q*b=Gcd(a,b)の他の整数解は、以下のように満たされる整数解を探す方法を上述した.
p = p0 + b/Gcd(a, b) * t
q=q 0-a/Gcd(a,b)*t(ここでtは任意の整数)
pa+qb=cの整数解については,p*a+q*b=Gcd(a,b)の各解にc/Gcd(a,b)を乗せればよい.
p*a+q*b=Gcd(a,b)の解p 0,q 0のセットが見つかった後、
p*a+q*b=cの解p 1=p 0*(c/Gcd(a,b)),q 1=q 0*(c/Gcd(a,b)),p*a+q*b=cの他の整数解が得られた.
p = p1 + b/Gcd(a, b) * t
q=q 1-a/Gcd(a,b)*t(ここでtは任意の整数)
p,qはp*a+q*b=cのすべての整数解である.
ここでは、(n-m)*t+k*l=x-y;
a=n-m;b = x- y;本題はa*t+k*l=b方程式tを満たす最小値を解くことであり、一次同余方程式a*t=b(mod l)の最小正整数解を求めることである.
手順:
<1>方程式a*t+k*l=bを書き出し,拡張ユークリッドEx_を利用する.EucGcd(Long long a,Long long l,Long long&x,Long long&y)は、最大公約数dを求める.
<2>解があるかどうかを判断し、b%d==0、解があり、解は存在するが唯一ではない!
<3>これは最小正の整数解を探す:x 1=x*(b/d)であり、最後の解:(x 1%(l/d)+l/d)%(l/d)である.
解の最小の正の整数解の参考資料を求めます:クリックしてリンクを開けます
拡張ユークリッドアルゴリズムの実現には2つあり、1つは反復法である.もう一つは再帰的で、理解しやすく、使いやすい!
反復法:

Long long Ex_EucGcd(Long long n, Long long m, Long long &x, Long long &y) {
		Long long x1 = 1, x2 = 0, x3 = n;
		Long long y1 = 0, y2 = 1, y3 = m;
		while (x3 % y3 != 0) {
			Long long d = n / m;
			Long long t1, t2, t3;
			t1 = x1 - d * y1; t2 = x2 - d * y2; t3 = x3 - d * y3;
			x1 = y1; x2 = y2; x3 = y3;
			y1 = t1; y2 = t2; y3 = t3;
		};
		x = y1; y = y2;
		return y3;
	}

再帰:

long long Extended_Gcd(long long a, long long b, long long &x, long long &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = Extended_Gcd(b, a%b, x, y);
    long long t = x - a/b * y;
    x = y;
    y = t;
    return d;
}

 
 
次は1061のコードです.
 

#include <iostream>

using namespace std;

long long Extended_Gcd(long long a, long long b, long long &x, long long &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = Extended_Gcd(b, a%b, x, y);
    long long t = x - a/b * y;
    x = y;
    y = t;
    return d;
}

int main()
{
    long long x, y, n, m, l;
    long long  a,b,c;
    long long x1,y1;
    while(cin>>x>>y>>m>>n>>l)
    {
        a = n - m;
        b = l;
        c = x - y;
        long long  M = Extended_Gcd(n-m, l, x1, y1);
        if( (c%M != 0) || (m == n) )
            cout<<"Impossible"<<endl;
        else
        {
            long long s;
            s = b/M;
            x1 = x1 * ( c/M );
            x1 = (x1%s + s )%s;
            cout<<x1<<endl;
        }

    }
    return 0;
}