2010年3月31日

#include <iostream>
using namespace std;
__int64 extgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b==0)
    {
        x=1,y=0;return a;
    }
    __int64 r=extgcd(b,a%b,x,y);
    __int64 t=x; x=y; y=t-a/b*y;
    return r;
}
int main()
{
    __int64 x,y,m,n,l,k,t;
    __int64 a,b,c,d;
    while(scanf("%I64d%I64d%I64d%I64d%I64d",&x,&y,&n,&m,&l)!=EOF)
    {

        a=m-n;
        b=x-y;
        if(m-n<0)
        {
            a=-a;
            b=(-b+l)%l;
        }
        else b=(b+l)%l;
        d=extgcd(a,l,k,t);
        if(b%d) { printf("Impossible\n"); continue;}
        k=(k*(b/d)%l+l)%(l/d);

        printf("%I64d\n", k);
    }
    return 0;
}

A+C*X=B(%2^K)
C*X=B-A(%2^K)
令a=c,b=B-A,n=2^K;
 利用以下結(jié)論（具體證明見《算法導(dǎo)論）：
推論1：方程ax=b(mod n)對于未知量x有解，當(dāng)且僅當(dāng)gcd(a,n) | b。
推論2：方程ax=b(mod n)或者對模n有d個(gè)不同的解，其中d=gcd(a,n)，或者無解。
定理1：設(shè)d=gcd(a,n)，假定對整數(shù)x和y滿足d=ax+by(比如用擴(kuò)展Euclid算法求出的一組解)。如果d | b，則方程ax=b(mod n)有一個(gè)解x0滿足x0=x*(b/d) mod n 。特別的設(shè)e=x0+n，方程ax=b(mod n)的最小整數(shù)解x1=e mod (n/d)，最大整數(shù)解x2=x1+(d-1)*(n/d)。
定理2：假設(shè)方程ax=b(mod n)有解，且x0是方程的任意一個(gè)解，則該方程對模n恰有d個(gè)不同的解(d=gcd(a,n))，分別為：xi=x0+i*(n/d) mod n 。

a*x=b(%n) => a*x+n*y=b
d=ext_gcd(a,n,x0,y0)
最小整數(shù)解x1=(x0*(b/d)%n+n)%(n/d);
  

#include <iostream>
using namespace std;
__int64 exgcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
    if(b==0)
    {
        x=1;y=0;return a;
    }
    __int64 r=exgcd(b, a%b, x, y);
    __int64 t=x;x=y;y=t-a/b*y;
    return r;
}
int main()
{
    __int64 A,B,C,K;
    __int64 a,b,n,d,x,y,e;
    while(scanf("%I64d%I64d%I64d%I64d",&A,&B,&C,&K)!=EOF)
    {
        if(A==0 && B==0 && C==0 && K==0) break;
        a=C;
        n=((__int64)1<<K); //小心溢出
        b=B-A;
        d=exgcd(a, n, x, y);
        if(b%d) {printf("FOREVER\n"); continue;}
        e=x*(b/d)%n+n;
        printf("%I64d\n",e%(n/d));
    }
    return 0;
};