C. Success Rate
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 ≤ 109; 0 ≤ p ≤ q ≤ 109; 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.
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 void gcd(LL a, LL b, LL &d, LL &x, LL &y)
5 {
6 if (!b)
7 {
8 d = a;
9 x = 1;
10 y = 0;
11 }
12 else
13 {
14 gcd(b, a % b, d, y, x);
15 y -= x * (a / b);
16 }
17 }
18 LL t, x, y, p, q, g, a, b, c;
19 LL dealZero(LL t)
20 {
21 if (c % t || c / t < 0)
22 return -1;
23 return c / t;
24 }
25 LL divab(LL a, LL b) //整数相除向小的数取整(负数取整绝对值会变大)
26 {
27 double x = double(a) / b;
28 if (x >= 0)
29 return (LL)x;
30 return (LL)(x - 1 + 1e-9);
31 }
32 int main()
33 {
34 scanf("%lld", &t);
35 while (t--)
36 {
37 scanf("%lld%lld%lld%lld", &x, &y, &p, &q);
38 //(x+a)/(y+a+b)=p/q a=? b=? min(a+b)=?(a>=0 && b>=0)
39 LL t1 = q - p, t2 = -p;
40 //t1*a + t2*b = p*y - q*x
41 c = (LL)p * y - (LL)q * x;
42 if (t1 == 0)
43 {
44 printf("%lld
", dealZero(t2));
45 continue;
46 }
47 if (t2 == 0)
48 {
49 printf("%lld
", dealZero(t1));
50 continue;
51 }
52 gcd(t1, t2, g, a, b); //a*t1+b*t2=g
53 if (g < 0)
54 a = -a, b = -b, g = -g;
55 if (c % g)
56 {
57 printf("-1
");
58 continue;
59 }
60 a *= c / g % (t2 / g);
61 //b *= c / g;
62 //************************************这里a,b乘完后后面处理会爆longlong
63 a = a % (t2 / g); //将结果先缩小
64 b = (c - t1 / g * a) / t2; //会爆longlong
65 //a*t1+b*t2=c
66 //a*t1+k*t1*t2/g + b*t2 - k*t1*t2/g = c 变动相差一个t1,t2的最小共倍数t1*t2/g
67 //(a+k*t2/g)*t1 + (b-k*t1/g)*t2=c
68 //a+k*t2/g>=0 && b-k*t1/g>=0
69 //t2/g > 0 a>=-k*t2/g ==> a*g/t2>=-k ==> -a*g/t2<=k
70 //t2/g < 0 a>=-k*t2/g ==> a*g/t2<=-k ==> -a*g/t2>=k
71 printf("a:%lld t1:%lld b:%lld t2:%lld g:%lld c:%lld
", a, t1, b, t2, g, c);
72 LL mink, maxk, hasMink = false, hasMaxk = false;
73 t1 /= g;
74 t2 /= g;
75 if (t2 >= 0)
76 {
77 hasMink = true;
78 mink = divab(-a, t2);
79 }
80 else
81 {
82 hasMaxk = true;
83 maxk = divab(-a, t2);
84 }
85 //t1/g > 0 ==> b >= k*t1/g ==> b*g/t1 >= k
86 //t1/g > 0 ==> b >= k*t1/g ==> b*g/t1 <= k
87 LL tmp = divab(b, t1);
88 if (t1 >= 0)
89 {
90 if (hasMaxk)
91 maxk = min(maxk, tmp); //**************************若为负数要向小的数取整
92 else
93 maxk = tmp, hasMaxk = true;
94 }
95 else
96 {
97 if (hasMink)
98 mink = max(mink, tmp);
99 else
100 mink = tmp, hasMink = true;
101 }
102 //a+k*t2 + b - k*t1=a+b+k*(t2-t1)
103 if (hasMaxk && hasMink && maxk < mink)
104 {
105 printf("-1
");
106 continue;
107 }
108 printf("maxk:%lld hasMaxk:%lld mink:%lld hasMink:%lld
", maxk, hasMaxk, mink, hasMink);
109 LL t = t2 - t1;
110 if (t > 0)
111 {
112 if (hasMink)
113 {
114 printf("%lld
", a + b + mink * t);
115 continue;
116 }
117 if (hasMaxk)
118 {
119 printf("%lld
", a + b + min(maxk, 0LL) * t);
120 continue;
121 }
122 }
123 else
124 {
125 if (hasMaxk)
126 {
127 printf("%lld
", a + b + maxk * t);
128 continue;
129 }
130 if (hasMink)
131 {
132 printf("%lld
", a + b + max(mink, 0LL) * t);
133 continue;
134 }
135 }
136 }
137 return 0;
138 }