POJ 2115 C Looooops 【线性模方程】

题意：转化成c * x = b - a mod (2 ^ k)，解这个模线性方程的最小正整数解即可

Sample Input
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

Sample Output
0
2
32766
FOREVER

解方程：ax == b (mod n);【ax % n == b % n】
设线性模方程的一个解为x0
条件①：有d = gcd(a, n)
条件②：有d = ax1 + ny, 由扩展欧几里得(Egcd)得到x1的值
条件③：b % d == 0 (有解的条件)
则x0 = x1*(b/d);

证明：
因为：容易求得d = gcd (a, n), 则有d = ax1 + ny①(扩展欧几里得定理)
方程①2边同时模n得：d % n == ax1 % n②
又因为：b % d == 0, 即b是d的倍数;
所以(b/d)必为整数;
所以由②得： b % n == d*(b/d) % n == ax1*(b/d) % n == ax % n
所以很容易可以看出x = x1*(b/d)是方程的一个整数解，得证

参考文献：

C++代码
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long

L Egcd (L a, L b, L &x, L &y)    //扩展欧几里得
{
    L d, tp;
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    d = Egcd (b, a%b, x, y);
    tp = x;
    x = y;
    y = tp - (a/b)*y;
    return d;
}
void MLE (L a, L b, L n)    //解模线性方程
{
    L x, y, d;
    d = Egcd (a, n, x, y);
    if (b % d == 0)
    {
        L x0 = (b / d * x) % n + n;
        cout << x0 % (n/d) << endl;
//对于无数个解形成的一群余数：周期个数是d，周期长度是n/d，也就是最小正整数解在n/d里，这个听老师说过，但是忘了为什么，涉及到群的概念……
    }
    else puts ("FOREVER");    //无解
}
int main()
{
    L a, b, c;
    int k;
    while (cin >> a >> b >> c >> k)
    {
        if (!a && !b && !c && !k)
            break;
        MLE (c, b - a, 1LL << k);
    }
    return 0;
}

补充：软件开发 , C语言 ,