POJ 2115 C Looooops(擴展歐幾里得)

輾轉相除法（歐幾里得算法）

時間復雜度：在O(logmax(a, b))以內

int gcd(int a, int b)
{if (b == 0) return a;return gcd(b, a % b);
}

　　

擴展歐幾里得算法

時間復雜度和歐幾里得算法相同

int extgcd(int a, int b, int& x, int& y)
{int d = a;if (b != 0) {d = extgcd(b, a % b, y, x);y -= (a / b) * x;} else {x = 1; y = 0;}return d;
}

用于求ax+by=gcd(a,b)整數解，xy返回整數解，extgcd的返回值是ax+by的值。

題目：(A+x*C)%2^k=B 求x整數解。
解析:
x*C=B-A 的在mod(2^k)情況下的整數解
可以轉化成x*C+y*(2^k)=B-A的解
通過擴展歐幾里得算法求出x1*C+y1*(2^k)=gcd(c,2^k)的解x1,y1,d=x1*C+y1*(2^k)=gcd(c,2^k)
x1*C+y1*(2^k)=(B-A)(gcd(c,2^k)/(B-A))
(A-B)/gcd(c,2^k)*x1*C+(A-B)/gcd(c,2^k)*y1*(2^k)=B-A
x=(A-B)/gcd(c,2^k)*x1
y=(A-B)/gcd(c,2^k)*y1
要求的值為x,x可能是負數,所以要把x變到正整數。通過+(2^k)/d 再%(2^k)/d來變成正數。

?

#include <cstdio>long long extgcd(long long a, long long b, long long& x, long long& y)
{long long d = a;if (b != 0) {d = extgcd(b, a % b, y, x);y -= (a / b) * x;} else {x = 1; y = 0;}return d;
}int main()
{long long a, b, c, k;while (scanf("%lld%lld%lld%lld", &a, &b, &c, &k) != EOF) {if (a == 0 && b == 0 && c == 0 && k == 0) break;long long x, y;long long t = b - a;long long h = 1LL << k;　　//2^klong long g = extgcd(c, h, x, y);if (t % g != 0) {　　　　　　//no solutionprintf("FOREVER\n");continue;}x *= t / g;x = (x % (h / g) + (h / g)) % (h / g);//最小非負整數解printf("%lld\n", x);}return 0;
}