Codeforces Round#412 C Success Rate

本文主要是介绍Codeforces Round#412 C Success Rate，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： 给你x，y，p，q; 其中 x，y，p，q 代表的含义为   x/y,  p/q，让你求一个b，使得(x+a)/(y+b)=p/q;并且求得的b还是最小。

思路：其实这就相当于一个数学问题中求定义域的问题，因为x,y,p,q,a,b都是整数，我们可以这样转化       x+a=k*p,y+b=k*q;这样的解有很多个，为了求最小的b，那么当k最小的时候b最小，这时我们先把p，q化为互质 的数，再求最小的k，这时候求得的b就是最小的，这里有限制条件  其中  a>=0,a<=b,把上面的式子转化一下就可以求出来了。

答案就是  b=k*q-y;

还要注意使用long long 要不然会溢出。运用数学的思想，通过一些条件限制一下变量

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>using namespace std;
int gcd(int x,int y)
{return y==0?x:gcd(y,x%y);
}
int main()
{int T;cin>>T;while(T--){int x,y,p,q;cin>>x>>y>>p>>q;int temp=gcd(p,q);p=p/temp;q=q/temp;if(p==0){if(x==0) cout<<0<<endl;else cout<<-1<<endl;}else if(p==q){if(x==y) cout<<0<<endl;else cout<<-1<<endl;}else{int k1=(x/p)+(1&&(x%p));int k2=(y-x)/(q-p)+(1&&(y-x)%(q-p));int k=max(k1,k2);cout<<(x/p)<<"   "<<(x%p)<<"   "<<(1&&(x%p))<<endl;cout<<k1<<"   "<<k2<<"   "<<k<<endl;cout<<k*q-y<<endl;}}return 0;
}

这篇关于Codeforces Round#412 C Success Rate的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---