uva 10277 - Boastin' Red Socks(概率）

本文主要是介绍uva 10277 - Boastin' Red Socks(概率），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 10277 - Boastin' Red Socks

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

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

#include <stdio.h>
#include <string.h>
#include<math.h>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;
}

这篇关于uva 10277 - Boastin' Red Socks(概率）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---