题意分析

本题的场景是有一个装有红、黑两种颜色袜子的抽屉，袜子总数在 2 到 50000 之间，但具体数量未知，红、黑袜子各自的数量也未知。每次在黑暗中从抽屉里随机取出两只袜子，取出两只红色袜子的概率恰好是 $p/q$（$q > 0$ 且 $0 ≤ p ≤ q$）。题目给出多组 $p$ 和 $q$ 的值，要求根据这些概率信息，确定抽屉里红、黑袜子各有多少只。若有多个解，需选择袜子总数最少的解。输入以包含两个零的一行作为结束标志，对于每组输入，若有解则输出红、黑袜子的数量，无解则输出 “impossible”。

解题思路

设抽屉里红色袜子有 $x$ 只，袜子总数为 $n$ 只，那么黑色袜子有 $n - x$ 只。从 $n$ 只袜子中选 2 只的组合数为 $C(n, 2) = n * (n - 1) / 2$，从 $x$ 只红色袜子中选 2 只的组合数为 $C(x, 2) = x * (x - 1) / 2$。根据概率的定义，取出两只红色袜子的概率为 $C(x, 2) / C(n, 2)$，即 $(x * (x - 1)) / (n * (n - 1)) = p / q$。

解题的具体步骤如下：

1. 输入处理：不断读取 $p$ 和 $q$ 的值，直到输入为两个零为止。
2. 特殊情况处理：若 $p$ 等于 $q$，则说明所有袜子都是红色，此时红色袜子和黑色袜子的数量分别为 2 和 0；若 $p$ 等于 0，则说明没有红色袜子，此时红色袜子和黑色袜子的数量分别为 0 和 2。
3. 约分：为了简化计算，先求出 $p$ 和 $q$ 的最大公约数 $g$，然后将 $p$ 和 $q$ 都除以 $g$。
4. 枚举总数 $n$：从 2 到 50000 枚举袜子的总数 $n$，对于每个 $n$，计算 $n * (n - 1) / q$ 的值 $m$，若 $n * (n - 1)$ 能被 $q$ 整除，则继续下一步。
5. 计算红色袜子数量 $x$：根据概率公式计算 $m * p$ 的值，然后对其开方并取整得到 $x$，若 $x * (x - 1)$ 等于 $m * p$ 且 $x$ 不小于 2，则找到了一个解。
6. 输出结果：若找到解，则输出红色袜子和黑色袜子的数量；若枚举完所有可能的 $n$ 都没有找到解，则输出 “impossible”。

示例代码

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring> 
#include<cmath>
#include<queue>
using namespace std;
#define sf scanf
#define pf printf
#define INF 1<<29
#define eps 1e-6
const double PI=acos(-1.0);
#define lint __int64
#define LL long long 
#define ULLint unsigned long long //2^64-1>1.8*10^19
#define clr(x) memset(x,0,sizeof(x))
#define Clr(x) memset(x,-1,sizeof(x))

// 计算最大公约数
LL gcd(LL a , LL b){ 
    return b==0 ? a : gcd(b,a%b);
}

int main(){
    LL p,q;
    while(sf("%lld%lld",&p,&q)){
        if(!p && !q) break;
        if(p==q){
            pf("2 0\n"); 
            continue;
        }
        if(p==0){ 
            printf("0 2\n"); 
            continue;
        }
        LL g=gcd(p,q);
        p/=g; q/=g;
        LL i,j;
        for(i=2; i<=50000; i++)
            if(i*(i-1)%q==0){
                LL n=i*(i-1)/q;
                LL m=n*p;
                j=(LL)sqrt(m+0.5)+1;
                if(j*(j-1)==m && j>=2)
                    break;
            }
        if(i>50000)
            pf("impossible\n");
        else        
            pf("%lld %lld\n",j,i-j);
    }
    return 0;
}

注意事项

1. 数据类型：由于 $p$ 和 $q$ 可能很大，需要使用 $long long$ 类型来避免整数溢出。
2. 边界条件：要特别处理 $p$ 等于 $q$ 和 $p$ 等于 0 的特殊情况。
3. 枚举范围：袜子总数的枚举范围是 2 到 50000，需要确保不超出这个范围。
4. 开方计算：在计算红色袜子数量 $x$ 时，对 $m * p$ 开方后需要取整并加 1，然后再判断是否满足条件。
5. 约分：在计算之前先对 $p$ 和 $q$ 进行约分，可以简化计算过程。