3972133_ac_172ms_228k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>

__int64 a, b;

__int64 solve(__int64 num)
{
	__int64 ret = (__int64)sqrt((double)num);

	for (int i = 0; i < 3; i++, ret++)
	{
		if (ret * (ret - 1) == num)
		{
			return ret;
		}
	}
	return -1;
}

__int64 gcd(__int64 a, __int64 b)
{
	return a == 0 ? b : gcd(b % a, a);
}

int main()
{
	__int64 tot, tmp;

	while (scanf("%I64d%I64d", &a, &b) == 2)
	{
		if (a == 0 && b == 0)
		{
			break;
		}
		if (a == 0)
		{
			puts("0 2");
			continue;
		}
		__int64 g = gcd(a, b);
		a /= g;
		b /= g;
		for (tot = 2; tot <= 50000; tot++)
		{
			tmp = tot * (tot - 1);
			if (tmp % b != 0)
			{
				continue;
			}
			tmp /= b;
			tmp *= a;
			__int64 ans = solve(tmp);
			if (ans != -1 && ans <= tot)
			{
				printf("%I64d %I64d\n", ans, tot - ans);
				break;
			}
		}
		if (tot > 50000)
		{
			puts("impossible");
		}
	}
	return 0;
}