uva 10277 - Boastin' Red Socks(概率） - c++编程基础

题目大意：给出p和q，表示概率p/q，处理问题，有n双红袜子，m双白袜子，从中连续取两双袜子，两双袜子的颜色都是红色的概率为p/q。求n和m，不存在的话输出impossible。

解题思路：首先对p/q分式进行化简，然后枚举n + m的和（为q的倍数），判断条件，然后枚举n。

#include   
#include   
#include  
  
long long gcd(long long a, long long b) {  
    return b == 0   a : gcd(b, a % b);  
}  
  
int main() {  
    long long p, q;  
    while (scanf("%lld%lld", &p, &q), p || q) {  
        if (p == q) printf("2 0\n");  
        else if (p == 0) printf("0 2\n");  
        else {  
            long long g = gcd(p, q);  
            p /= g, q /= g;  
            long long i, j;  
            for (i = 2; i <= 50000; i++) {  
                if(i * (i - 1) % q == 0) {  
                    long long n = i * (i - 1) / q;  
                    long long m = n * p;  
                    j = (long long) sqrt(m + 0.5);  
                    if (j * (j + 1) == m && j + 1 >




= 2)  
                        break;  
                }  
            }  
  
            if (i <= 50000)  
                printf("%lld %lld\n", j + 1, i - j - 1);  
            else   
                printf("impossible\n");  
        }  
    }  
    return 0;  
}