2015年1月2日 星期五

2014/01/02 vijos P1009 清帝之惑之康熙

/*
    模逆元
    是說 X,Y 貌似不一定 <L 啊 囧
*/
// https://vijos.org/p/1009
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;

ll x, y, m, n, L;

ll gcd(ll a, ll b)
{
    while( a && b )
    {
        if( a < b ) swap(a, b);
        a %= b;
    }
    return a+b;
}

ll rev(ll x, ll y)
{
    if( x == 0 ) return 0;
    else
    {
        return ((1-y*rev(y%x, x) )/x+y)%y;
    }
}

int main()
{
    cin>>x>>y>>m>>n>>L;

    ll A = ((m-n)%L+L)%L;
    ll B = L;
    ll C = ((y-x)%L+L)%L;

    ll GCD = gcd(gcd(A, B), C);
    A /= GCD; B /= GCD; C /= GCD;

    if( gcd(A, B) != 1 ) puts("Impossible");
    else
    {
        ll d = rev(A, B)*C%B;
        cout<<d<<endl;
    }
}

沒有留言:

張貼留言