3801525_ac_0ms_208k.cpp

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

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

using namespace std;

struct node
{
	unsigned __int64 a, r;
};

vector <node> num;

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

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

triple Extended_Euclid(unsigned __int64 a,unsigned __int64 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;
}

unsigned __int64 MLES(unsigned __int64 a,unsigned __int64 b,unsigned __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()
{
	unsigned __int64 A, B, C, W;

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