1787.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1787 on 2006-07-19 at 15:44:54 */ 
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

typedef long long int64;

int64 x, y;

void extend_gcd(int64, int64, int64);
inline int64 ci(int64, int64);

int main()
{
	int64 a, b, c, k;

	while(scanf("%lld %lld %lld %lld", &a, &b, &c, &k) != EOF && k != 0) {
		k = (int64)1 << k; a -= b;
		int64 f = __gcd(k, c);
		if(a == 0) { printf("0\n"); continue; }
		else if(c == 0 || a%f != 0) { printf("FOREVER\n"); continue; }
		c /= f; k /= f; a /= f;
		extend_gcd(k, c, a);
		printf("%lld\n", k*max(ci(-x, c), ci(y, k))-y);
	}
	
	return 0;
}

void extend_gcd(int64 a, int64 b, int64 d)
{
	if(b == 0) { x = d / a; y = 0; }
	else {
		extend_gcd(b, a%b, d);
		int64 tx = x, ty = y;
		x = ty; y = tx - a/b*ty;
	}
}
int64 ci(int64 a, int64 b)
{
	int64 r = (a+b-1)/b;
	return r >= 0 ? r : r-1;
}