POJ-2115CLooooops（扩展欧几里得）

Description

for (variable = A; variable != B; variable += C)

  statement;

Input

Output

Sample Input

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

Sample Output

0
2
32766
FOREVER

题目大意：给你一个程序 for(variable = A; variable%(2^k) != B; variable += C) ，题目给出A，B，C，k。问你这个程序如果能终止，最多循环多少次，如果不能终止输出：“FOREVER”。

题目思路：直接模拟这个程序肯定是不行的，根据这个程序我们可以列出一个等式 (A + x*C)%(2^k) = B; 此处的x便是我们所要求的答案，我们再把这个等式进行一些变换可以得到：A + x*C = B + (2^k)*y -> C*x - (2^k)*y = B - A;便得到了一个形如ax+by=c的等式了，接下来只需要借助扩展欧几里得算法，便可以很轻松地求得答案了。（注意，这里的结果和y的正负无关，所以转换的时候b可以直接等于(2^k)）。

AC代码如下：

#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
#define FIN freopen("in.txt","r",stdin)
#define fuck(x) cout<<'['<using namespace std;
typedef long long LL;
typedef pairpii;
const int MX = 100 + 10;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if(!b) {
        d = a;
        x = 1;
        y = 0;
    } else {
        ex_gcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

LL solve(LL a, LL b, LL c) {
    LL d = gcd(a, b);
    if(c % d)
        return -1;//若方程无解，则说明无法退出循环，返回-1；
    else {
        a /= d;
        b /= d;
        c /= d;
        LL D, x, y;
        ex_gcd(a, b, D, x, y);
        x = (x * c) % b;//扩展解系，求得最小的x；
        while(x <0)
            x += b;
        return x;
    }
}

LL A, B, C;
int k;

int main() {
    //FIN;
    while(cin >> A >> B >> C >> k) {
        if(A == 0 && B == 0 && C == 0 && k == 0) break;
        LL b = (LL)1 <        LL a = C, c = B - A;
        LL ans = solve(a, b, c);
        if(ans == -1)
            puts("FOREVER");
        else
            cout <    }
    return 0;
}