1391.cpp

来自「这是哈尔滨工业大学acmOJ的源代码」· C++ 代码 · 共 44 行

/*  This Code is Submitted by wywcgs for Problem 1391 on 2006-01-11 at 01:01:24 */ 
#include <cstdio>
#include <cmath>

const int MAX = 50000;
typedef long long int64;

int64 gcd(int64, int64);
bool analyze(int64, int64&);

int main()
{
	int64 p, q, x, y;
	
	while(scanf("%lld %lld", &p, &q) != EOF && q != 0) {
		if(p == 0) printf("0 2\n");
		else {
			int64 d = gcd(p, q);
			p /= d; q /= d;
			for(y = 2; y <= MAX; y++)
				if(y*(y-1)%q == 0 && analyze(y*(y-1)/q*p, x)) break;
			if(y <= MAX) printf("%lld %lld\n", x, y-x);
			else printf("impossible\n");
		}
	}
	
	return 0;
}

int64 gcd(int64 a, int64 b)
{
	if(a % b == 0) return b;
	else return gcd(b, a%b);
}
bool analyze(int64 m, int64& r)
{
	int64 x = (int64)(sqrt(4*m+1)+1e-5);
	if(x*x != 4*m+1 || x%2 == 0) return false;
	else {
		r = (x + 1) / 2;
		return true;
	}
}