You are an experienced Codeforces user. Today you found out that during your activity on Codeforces you have made?y?submissions, out of which?x?have been successful. Thus, your current success rate on Codeforces is equal to?x?/?y.

Your favorite rational number in the?[0;1]?range is?p?/?q. Now you wonder: what is the smallest number of submissions you have to make if you want your success rate to be?p?/?q?

Input

The first line contains a single integer?t?(1?≤?t?≤?1000)?— the number of test cases.

Each of the next?t?lines contains four integers?x,?y,?p?and?q?(0?≤?x?≤?y?≤?10⁹;?0?≤?p?≤?q?≤?10⁹;?y?>?0;?q?>?0).

It is guaranteed that?p?/?q?is an irreducible fraction.

Hacks.?For hacks, an additional constraint of?t?≤?5?must be met.

Output

For each test case, output a single integer equal to the smallest number of submissions you have to make if you want your success rate to be equal to your favorite rational number, or?-1?if this is impossible to achieve.

Example

Input 4
3 10 1 2
7 14 3 8
20 70 2 7
5 6 1 1 Output 4
10
0
-1

Note

In the first example, you have to make 4 successful submissions. Your success rate will be equal to?7?/?14, or?1?/?2.

In the second example, you have to make 2 successful and 8 unsuccessful submissions. Your success rate will be equal to?9?/?24, or?3?/?8.

In the third example, there is no need to make any new submissions. Your success rate is already equal to?20?/?70, or?2?/?7.

In the fourth example, the only unsuccessful submission breaks your hopes of having the success rate equal to 1.

題目鏈接：

CodeForces - 807C?

題意：給你4個整數(shù)，x,y,p,q，P/Q的范圍是[0,1]，讓你求最小的提交數(shù)量b，其中a個提交成功使 ( x + a ) / ( y + b ) == p / q

我們設(shè)一個系數(shù)n，使

p*n=x+a

q*n=y+b

那么，

a=p*n-x

b=q*n-y

根據(jù)題意，我們知道a和b滿足的條件為b>=a>=0

并且觀察可知a和n呈正相關(guān)，那么我們要求最小的a，可以通過二分n來得到

根據(jù)題目的數(shù)據(jù)范圍，n的二分區(qū)間為0~1e9

注意下-1的情況就行了。

細節(jié)看我的AC代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define gg(x) getInt(&x) using namespace std; typedef long long ll; inline void getInt(int* p); const int maxn=1000010; const int inf=0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int t; ll x,y,a,b; int main() {gbtb;cin>>t;while(t--){cin>>x>>y>>a>>b;ll l=0;ll r=1e9;ll mid;ll ans=-1;while(l<=r){mid=(l+r)>>1;ll a1=a*mid-x;ll a2=b*mid-y;if(a1>=0&&a2>=0&&(a1<=a2)){ans=mid;r=mid-1;}else{l=mid+1;}}if(ans==-1){cout<<-1<<endl;}else{cout<<b*ans-y<<endl;}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/10272282.html

總結(jié)

以上是生活随笔為你收集整理的Success Rate CodeForces - 807C （数学+二分）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。