|
题目大意：给出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;
}
?
?
|