最后化成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 阅读(1515)
评论(2) 编辑 收藏 引用 所属分类:
Algorithm - Number Theory