pku2115.cpp

这是ACM 方面的资料 是PKU的 北京大学的出来的

#include <stdio.h>

__int64 pow2c;
__int64 E_gcd(__int64 a, __int64 b, __int64 &x, __int64 &y)
{
	__int64 x1, y1, p;
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}

	p = E_gcd(b, a % b, x1, y1);

	x = y1;
	y = x1 - (a / b) * y1;
	return p;
}

__int64 Pow2(int c)
{
	__int64 ans;
	int i;
	ans = 1;
	for (i = 0; i < c; i++)
	{
		ans *= 2;
	}
	return ans;
}

void Calc(int a1, int a2, int b, int c)
{
	__int64 m, n, q, x, y, gcd, lcm, ans;
	q = a2 - a1;
	q = (q + pow2c) % pow2c;
	m = b;
	n = pow2c;
	
	gcd = E_gcd(m, n, x, y);
	
	if (q % gcd != 0)
	{
		printf("FOREVER\n");
	}
	else
	{
		q /= gcd;
		n /= gcd;
		ans = ((q * x) % n + n) % n;
		printf("%I64d\n", ans);
	}
}

int main()
{
	int A, B, C, D, E;
	while (scanf("%d %d %d %d", &A, &B, &C, &D) != -1 && (A + B + C + D))
	{
		pow2c = Pow2(D);
		Calc(A, B, C, D);
	}
	return 0;
}