C Looooops解题报告，线性同余

时间：2010-09-25 来源：ronaflx

学习数学呀，学习新的知识。

题目描述的就是一个C * x + (1 << k) * y = B - A的方程组。

用一般的方式就似乎对于一个一般的A * X + B * Y = C（1）的方程组

我们先求D = GCD(A,B)如果C % D == 0那么一定可以求解，否则等式的右边是一个分数，该方程无解。

现在变为求 A1 * X + B1 * Y = C / D（2）

因为已经求过GCD了，所以现在的GCD(A1,B1) == 1

所以根据扩展GCD可以求得X1 * A1 + Y1 * B1 = 1的X,Y那么X * C / D,与 Y * C / D就是方程（1），（2）的解了

可以得到一个解系X = X1 * C / D + B1 * T Y = Y1 * C / D - A1 * T 题目的要求是求解最小正X

所以 X = (X1 * C / D % B1 + B1) % B1

#include <iostream>
using namespace std;

long long extended_euclid(long long a,long long b,long long &x,long long &y)
{
    long long ret;
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ret = extended_euclid(b,a%b,x,y);
    long long t = x;
    x = y;
    y = t - a / b * y;
    return ret;
}
long long modular_linear(long long a,long long b,long long c)// a * x + b * y = c
{
    long long x,y;
    long long d = extended_euclid(a,b,x,y);
    if (c%d)
        return -1;
    long long b1 = b / d;
    return (x * (c / d) % b1 + b1) % b1;
}

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

相关阅读更多 +