poj 2115 C Looooops(モード線形方程式)

http://poj.org/problem?id=2115
题意:Cのサイクル(for i=A;i!=B;i+=C)について、kビットストレージシステム内で何回サイクルが终わるかを寻ねる.
サイクル数が限られていれば出力回数を終了でき、そうでなければ出力 FOREVER;
解:xをサイクル回数とする;
　  (A+C*x)%2^k = B;　　
C*x+A=2^k*y+B; 
だからC*x-2^k*y=B-A;a*x+b*y=c(またはa*x=c(mod b))モード線形方程式の形式と同様に,拡張ユークリッドアルゴリズムに基づいてテンプレート問題を解決した.

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#define LL long long
#define _LL __int64
#define eps 1e-8

using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 10;

/*
(A+C*x)%2^k = B;
   A + C*x = 2^k * y + B;
C*x - 2^k*y = B-A;
*/

LL extend_gcd(LL a, LL b, LL &x, LL &y)
{
	if(b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	LL d = extend_gcd(b,a%b,x,y);
	LL t = x;
	x = y;
	y = t - a/b*y;
	return d;
}

int main()
{
	int A,B,C,k;
	LL a,b,c;
	LL x,y;

	while(~scanf("%d %d %d %d",&A,&B,&C,&k))
	{
		if(A == 0 && B == 0 && C == 0 && k == 0)
			break;
		a = C;
		b = 1LL<<k;
		c = B-A;

		LL d = extend_gcd(a,b,x,y);
		if(c%d != 0)
		{
			printf("FOREVER
");
			continue;
		}
		x = x * (c/d);
		x = (x%(b/d) + (b/d)) % (b/d);
		printf("%lld
",x);

	}
	return 0;
}