模线性方程----zoj_2305

    推论1：方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,n) | b。
    推论2：方程ax=b(mod n)或者对模n有d个不同的解，其中d=gcd(a,n)，或者无解。
    定理1：设d=gcd(a,n)，假定对整数x和y满足d=ax+by(比如用扩展Euclid算法求出的一组解)。如果d | b，则方程ax=b(modn)有一个解x0满足x0=x*(b/d) mod n 。特别的设e=x0+n，方程ax=b(mod n)的最小整数解x1=e mod(n/d)，最大整数解x2=x1+(d-1)*(n/d)。
    定理2：假设方程ax=b(mod n)有解，且x0是方程的任意一个解，则该方程对模n恰有d个不同的解(d=gcd(a,n))，分别为：xi=x0+i*(n/d) mod n 。
    以上定理的具体证明见《算法导论》。

    实用模板

    扩展欧几里德算法

 int Extended_Euclid(int a,int b,int& x,int &y)
 {
     if(b==0){
         x=1;
         y=0;
         return a;
     }
     int d=Extended_Euclid(b,a%b,x,y);
    int temp=x;x=y;y=temp-a/b*y;
    return d;
}

 用扩展欧几里得解模线性方程ax=b (mod n)

 

bool modularLinearEquation(int a,int b,int n)
 {
     int x,y,x0,i;
     int d=Extended_Euclid(a,n,x,y);
     if(b%d) 
            return false;
         x0=x*(b/d)%n;
     for(i=1;i<=d;i++)
       printf("%d\n",(x0+i*(n/d))%n);
    return true;
}

zoj_2305(这里是求最小解)

#include <cstdio> 

 

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

long long modular_linear(long long a,long long b,long long n)
{
    long long x,y;
    long long d = exgcd(a,n,x,y);
    if (b % d)
    {
        return -1;
    }
    long long re = x*(b/d) %n + n;
    re = re%(n /d);
    return re;
}

int main()
{
    long long A,B,C,K;
    while (scanf("%lld %lld %lld %lld",&A,&B,&C,&K)== 4 &&(A||B||C||K))
    {
        long long jud = modular_linear(C,B-A,1LL << K);
        if (jud == -1)
            printf("FOREVER\n");
        else
            printf("%lld\n",jud);
    }
    return 0;
}