poj 2115 C Looooops

 這個題目就是解線性同余方程，(a + n*c) % 2的k次 = b % 2的k次。既然以前是學信安的，對數論本來就不排斥，最近還好好看了下算
法導論。這個方程轉換為n*c = (b-a) % 2的k次。根據數論的知識，  ax = b%n，需要保證gcd(a,n)|b，意思b是gcd(a,n)的倍數，這個
一下子也很難解釋清楚啊，不滿足這個條件，就是沒解了。還有，如果有解的話，解的個數就是d = gcd(a,n)。而且其中一個解是x0 = x'(b
/ d)，其中x'是用擴展歐幾裡德算法求出來的，滿足關系式a*x'+n*y'=d。
   但是這個題不僅僅用到數論的這些知識，因為必須求滿足條件的最小解，而如果有解的話是d個，而且滿足解x = x0 + i(b/d)，
（1<=i<=d)。既然要求最小的解，那麼對解mod(n/d)即可了，因為它們之間的差都是n/d的倍數。

   代碼如下：

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;

//擴展歐幾裡德算法
//d = a * x + b * y，d是a和b的最大公約數
long long egcd(long long a, long long b, long long& x, long long& y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        long long nRet = egcd(b, a % b, x, y);
        long long t = x;
        x = y;
        y = t - (a / b) * y;
        return nRet;
    }
}

int main()
{
    long long nA, nB, nC, nK;

    while (scanf("%I64d%I64d%I64d%I64d", &nA, &nB, &nC, &nK),
            nA || nB || nC || nK)
    {
        long long x, y;
        long long n = pow((double)2, (double)nK) + 1e-8;
        long long d = egcd(n, nC, x, y);
        long long b = (nB - nA + n) % n;
        if (b % d)//如果d | b失敗
        {
            printf("FOREVER\n");
        }
        else
        {
            //printf("y:%I64d, b:%I64d, d:%I64d n:%I64d\n", y, b, d, n);
            y = (y + n) % n;
            long long ans = (y * (b / d)) % (n / d);
            printf("%I64d\n", ans);
        }
    }

    return 0;
}