题目链接:http://poj.org/problem?id=2645
题目大意
给定p和q，意指
从其中拿出两只袜子其颜色
都是红色的概率是p/q,
问在袜子总数最少的情况下其红色和
黑色袜子的数量是多少。
题目分析
不难把式子列出来：
p/q=x*(x-1)/(y*(y-1)),
发现总数范围是50000，
尝试者暴力枚举y，
左边式子实质上是p*k/(q*k),
那么我们可以得到k，然后通过sqrt
把x得到，下面只要验证x*(x-1)
是否等于q*k即可，其中一些精度细节见代码。
还有个点就是x要至少为2，数量上有个小坑。
然后就是特判下p为零的情况。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll unsigned long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
int mod=20100501;
const int maxn=30+10;
const int ub=1e6;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意：
给定p和q，意指
从其中拿出两只袜子其颜色
都是红色的概率是p/q,
问在袜子总数最少的情况下其红色和
黑色袜子的数量是多少。题目分析：
不难把式子列出来：
p/q=x*(x-1)/(y*(y-1)),
发现总数范围是50000，
尝试者暴力枚举y，
左边式子实质上是p*k/(q*k),
那么我们可以得到k，然后通过sqrt
把x得到，下面只要验证x*(x-1)
是否等于q*k即可，其中一些精度细节见代码。
还有个点就是x要至少为2，数量上有个小坑。
然后就是特判下p为零的情况。
*/
ll p,q;
int main(){while(scanf("%I64d%l64d",&p,&q)&&(p||q)){ll gd=gcd(p,q);p/=gd,q/=gd;if(p==0) {puts("0 2");continue;}ll i=1,k,tp,x=-1,y=-1,tmp;for(y=2;y<=50000;y++){if(y*(y-1)%q) continue;tp=y*(y-1)/q;k=(ll)sqrt(1.0*p*tp+0.5)+1;if(k*(k-1)==(p*tp)&&k>=2){x=k;break;}}if(x==-1) puts("impossible");else printf("%I64d %I64d\n",x,y-x);}return 0;
}