這個(gè)題目就是解線性同余方程，(a + n*c) % 2的k次 = b % 2的k次。既然以前是學(xué)信安的，對(duì)數(shù)論本來(lái)就不排斥，最近還好好看了下算
法導(dǎo)論。這個(gè)方程轉(zhuǎn)換為n*c = (b-a) % 2的k次。根據(jù)數(shù)論的知識(shí)， ax = b%n，需要保證gcd(a,n)|b，意思b是gcd(a,n)的倍數(shù)，這個(gè)
一下子也很難解釋清楚啊，不滿足這個(gè)條件，就是沒(méi)解了。還有，如果有解的話，解的個(gè)數(shù)就是d = gcd(a,n)。而且其中一個(gè)解是x0 = x'(b
/ d)，其中x'是用擴(kuò)展歐幾里德算法求出來(lái)的，滿足關(guān)系式a*x'+n*y'=d。
但是這個(gè)題不僅僅用到數(shù)論的這些知識(shí)，因?yàn)楸仨毲鬂M足條件的最小解，而如果有解的話是d個(gè)，而且滿足解x = x0 + i(b/d)，
（1<=i<=d)。既然要求最小的解，那么對(duì)解mod(n/d)即可了，因?yàn)樗鼈冎g的差都是n/d的倍數(shù)。
代碼如下：
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
//擴(kuò)展歐幾里德算法
//d = a * x + b * y，d是a和b的最大公約數(shù)
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;
}