【codeforces 807C】Success Rate
Codeforces rate success
2023-09-14 09:03:50 时间
【题目链接】:http://codeforces.com/contest/807/problem/C
【题意】
给你4个数字
x y p q
要求让你求最小的非负整数b;
使得
(x+a)/(y+b)==p/q
同时a为一个整数且0<=a<=b
【题解】
/*
(x+a)/(y+b)==p/q;
则
x+a=np
y+b=nq
(以上结论只在p和q是互质的情况下有效,当然题目有说p和q互质)
a=np-x
b=nq-y
a<=b
因为p<q所以n越大b会越大;
又p和q都大于等于0,所以n越大,a和b都是不下降的
二分n
*/
【Number Of WA】
3
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 110;
int t;
LL x,y,p,q;
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
cin >> t;
while (t--)
{
cin >> x >> y >> p >> q;
LL l = 0,r = 1e9,ans = -1;
while (l<=r)
{
LL mid = (l+r)>>1;
LL a=mid*p-x,b=mid*q-y;
if (a>=0 && b>=0 && a<=b)
{
ans = mid;
r = mid-1;
}
else
l = mid+1;
}
if (ans==-1)
cout <<-1<<endl;
else
cout <<ans*q-y<<endl;
}
return 0;
}
相关文章
- CodeForces 91A Newspaper Headline
- 【Codeforces 449A】Jzzhu and Chocolate
- 【Codeforces 140A】New Year Table
- 【Codeforces 350B】Resort
- 【Codecraft-18 and Codeforces Round #458 (Div. 1 + Div. 2, combined) C】 Travelling Salesman and Special Numbers
- 【Educational Codeforces Round 35 A】 Nearest Minimums
- 【31.58%】【codeforces 719B】 Anatoly and Cockroaches
- 【27.34%】【codeforces 611D】New Year and Ancient Prophecy
- 【43.75%】【codeforces 688E】The Values You Can Make
- 【codeforces 762B】USB vs. PS/2
- 【codeforces 754B】 Ilya and tic-tac-toe game
- 【codeforces 572B】Order Book
- 【Codeforces Round #428 (Div. 2) A】Arya and Bran
- 【codeforces 812C】Sagheer and Nubian Market
- Codeforces Round #433 (Div. 2, based on Olympiad of Metropolises)
- Codeforces Round #427 (Div. 2)
- Codeforces Round #415 (Div. 2) 翻车啦