最后化成c * x = b - a mod (2 ^ k)，解這個模線性方程，輸出最小正解即可。
寫程序的時候有了一個誤區，以為如果b - a是負的，把它化成正的話那么輸出的時候就可以直接模2 ^ k，不用再考慮是負的情況了。但是忽略了x可能為負的情況，所以WA了很多次。其實根本不需考慮b - a的正負性，最后輸出的時候加2 ^ k再模2 ^ k就行了。
還有一個是輸出最小解，因為最后的所有解模n / d同余，因此直接模n / d即可。
#include <cstdio>
//ax + by = gcd(a, b)
long long extended_gcd(long long a, long long b, long long &x, long long &y)
{
long long ret, tmp;
if (!b)
{
x = 1, y = 0;
return a;
}
ret = extended_gcd(b, a % b, x, y);
tmp = x;
x = y;
y = tmp - a / b * y;
return ret;
}
//ax = b mod n
long long modular_linear_equation(long long a, long long b, long long n)
{
long long x, y, e;
long long d = extended_gcd(a, n, x, y);
if (b % d) return -1;
e = b / d * x % n + n;
return e % (n / d);
}
int main()
{
long long a, b, c, ans;
int k;
while (scanf("%lld %lld %lld %d", &a, &b, &c, &k) == 4)
{
if (a == 0 && b == 0 && c == 0 && k == 0)
break;
ans = modular_linear_equation(c, b - a, 1LL << k);
if (ans == -1)
puts("FOREVER");
else
printf("%lld\n", ans);
}
return 0;
}
posted on 2009-03-17 18:53
sdfond 閱讀(1547)
評論(2) 編輯 收藏 引用 所屬分類:
Algorithm - Number Theory