pku2645.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 76 行

#include <stdio.h>

typedef long long llong;

llong v[50002];
llong a, b;

llong Gcd(llong a, llong b)
{
	return b == 0 ? a : Gcd(b,a%b);
}

void init()
{
	llong i;
	for (i = 0; i <= 50001; i++)
		v[i] = i * (i - 1) / 2;
}

int find(llong key)
{
	int low, high, mid;
	low = 0;
	high = 50001;
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (v[mid] == key)
			return mid;
		if (v[mid] < key)
			low = mid + 1;
		else
			high = mid - 1;
	}
	return -1;
}

void Solve()
{
	int i, pos;
	llong gcd, tmp;
	gcd = Gcd(b,a);
	a /= gcd;
	b /= gcd;
	if (a == 0)
	{
		printf("0 2\n");
		return;
	}
	else if (a == b)
	{
		printf("2 0\n");
		return;
	}
	for (i = 2; i < 50001; i++)
	{
		if (v[i] % b != 0)
			continue;
		tmp = v[i] / b * a;
		pos = find(tmp);
		if (pos > 0)
		{
			printf("%d %d\n", pos, i - pos);
			return;
		}
	}
	printf("impossible\n");
}

int main()
{
	init();
	while (EOF != scanf("%I64d%I64d", &a, &b) && (a||b))
		Solve();
}