3801424_wa.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 107 行

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n;
struct node
{
	__int64 a, r;
};

vector <node> num;

__int64 mod(__int64 a,__int64 b)
{
	if(a >= 0)
      return a % b;
	else
      return a % b + b;
}

__int64 gcd(__int64 a,__int64 b)
{
	if(b == 0)
		return a;
	else
		return gcd(b,mod(a,b));
}

__int64 lcm(__int64 a,__int64 b)
{
	return a*b/gcd(a,b);
}

struct triple
{
	__int64 d,x,y;
};

triple Extended_Euclid(int a,int b)
{
	triple result;
	
	if(b == 0)
	{
		result.d = a;
		result.x = 1;
		result.y = 0;
	}
	else
	{
		triple ee = Extended_Euclid(b,mod(a,b));
		result.d = ee.d;
		result.x = ee.y;
		result.y = ee.x - (a/b)*ee.y;
	}
	return result;
}

__int64 MLES(__int64 a,__int64 b,__int64 n)
{
	triple ee = Extended_Euclid(a,n);
	
	if(mod(b,ee.d) == 0)
		return mod((ee.x * (b / ee.d)),n / ee.d);
	else
		return -1;
}

int main()
{
	int i;
	node t;
	__int64 A, B, C, W;

	while(true)
	{
		scanf("%I64d%I64d%I64d%I64d", &A, &B, &C, &W);
		if (W == 0)
		{
			break;
		}
		W = ((__int64)1) << W;
		B = (B - A + W) % W;
		if (C == 0)
		{
			if (B == 0)
			{
				puts("0");
			}
			else
			{
				puts("FOREVER");
			}
			continue;
		}
		__int64 ans = MLES(C, B, W);
		if (ans == -1)
			puts("FOREVER");
		else
			printf("%I64d\n", ans);
	}
	return 0;
}