首页 > 代码库 > UVA10277 - Boastin' Red Socks(枚举+二分)
UVA10277 - Boastin' Red Socks(枚举+二分)
UVA10277 - Boastin‘ Red Socks(枚举+二分)
题目链接
题目大意:现在有m只红袜子,n只黑袜子,这样总袜子total = n + m;现在给你p, q,确定n和m,使得从这些袜子中取两只都是红袜子的概率等于p/q;如果没有这样的n和m满足要求输出impossible;
解题思路:m *
(m - 1) / (total *
(total - 1)) = p /q; 那么我们只需要枚举total,就可以解到m。但是会有精度误差,貌似有解决的办法,但是觉得没法理解。后面看了另外的一种题接,二分m,因为m > 1之后就是单调递增的。所以只要之前处理掉特殊情况 m = 0,也就是p = 0的情况就可以了。
代码:
#include <cstdio>
#include <cstring>
#include <cmath>
typedef long long ll;
ll gcd (ll a, ll b) {
return (b == 0) ? a : gcd(b, a%b);
}
int main () {
ll p, q, ans, P, Q;
bool flag;
while (scanf ("%lld%lld", &P, &Q) != EOF && (P || Q)) {
flag = 0;
if (P == 0) {
printf ("0 2\n");
continue;
}
if (P == Q) {
printf("2 0\n");
continue;
}
ans = gcd(P, Q);
P /= ans;
Q /= ans;
ll m, total;
int l, r;
for (total = 3; total <= 50000; total++) {
ll N = total * (total - 1) * P, M;
if (N % Q != 0)
continue;
N /= Q;
l = 1; r = total;
while (l < r) {
m = (l + r) / 2;
M = m * (m - 1);
if (M < N)
l = m + 1;
else if (M > N)
r = m;
else {
flag = 1;
break;
}
}
if (flag)
break;
}
if (flag)
printf ("%lld %lld\n", m, total - m);
else
printf ("impossible\n");
}
return 0;
}
UVA10277 - Boastin' Red Socks(枚举+二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。