数論のユークリッドアルゴリズム(四)

概要:ユークリッドアルゴリズムの応用
タイトルリンク:poj 1061
解題の構想:A=m-n,B=y-x,N=L,題目は解くモードの線形方程式Ak≡B(mod N)の前処理に転化します:もしmはnより小さいならば、mとnを交換して、xとy
コード:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

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

int main()
{
    long long x,y,m,n,L,ans;
    while(~scanf("%lld %lld %lld %lld %lld",&x,&y,&m,&n,&L))
    {
        if(m<n)
        {
            swap(x,y);
            swap(m,n);
        }

        long long a=m-n,b=y-x,X,Y;
        if(b<0) b+=L;      //    
        long long d=extend_gcd(a,L,X,Y);
        if(b%d==0)
        {
            X%=L,X+=L,X%=L;
            ans=X*(b/d)%(L/d);
        }
        else
            ans=-1;

        if(ans==-1)
            printf("Impossible
");
        else
            printf("%lld
",ans);
    }

    return 0;
}