【codeforces 807C】Success Rate

【题目链接】: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=npy+b=nq(以上结论只在p和q是互质的情况下有效,当然题目有说p和q互质)a=np-xb=nq-ya<=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 usecin >> 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;}elsel = mid+1;}if (ans==-1)cout <<-1<<endl;elsecout <<ans*q-y<<endl;}return 0; }

转载于:https://www.cnblogs.com/AWCXV/p/7626335.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的【codeforces 807C】Success Rate的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。