C. Success Rate

Codeforces

IDCF807C

Time2000ms

Memory256MB

Difficulty—

binary searchmath

English · Original

Chinese · Translation

Formal · Original

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. [samples] ## 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 用户。今天你发现，在你于 Codeforces 上的活动中，你一共提交了 #cf_span[y] 次，其中 #cf_span[x] 次成功。因此，你在 Codeforces 上的当前成功率是 #cf_span[x / y]。你最喜欢的区间 #cf_span[[0;1]] 内的有理数是 #cf_span[p / q]。现在你想知道：为了让你的成功率变为 #cf_span[p / q]，你最少需要再提交多少次？第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]；#cf_span[0 ≤ p ≤ q ≤ 10^9]；#cf_span[y > 0]；#cf_span[q > 0])。保证 #cf_span[p / q] 是一个最简分数。 *黑客测试*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。对于每个测试用例，输出一个整数，表示你为了使成功率等于你最喜欢的有理数所需做的最少提交次数；如果无法实现，则输出 _-1_。在第一个例子中，你需要再做 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。在第二个例子中，你需要再做 2 次成功提交和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。在第三个例子中，无需做任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。在第四个例子中，唯一的失败提交破坏了你获得成功率为 1 的希望。 ## Input 第一行包含一个整数 #cf_span[t] (#cf_span[1 ≤ t ≤ 1000]) —— 测试用例的数量。接下来的 #cf_span[t] 行，每行包含四个整数 #cf_span[x], #cf_span[y], #cf_span[p] 和 #cf_span[q] (#cf_span[0 ≤ x ≤ y ≤ 10^9]；#cf_span[0 ≤ p ≤ q ≤ 10^9]；#cf_span[y > 0]；#cf_span[q > 0])。保证 #cf_span[p / q] 是一个最简分数。*黑客测试*。对于黑客测试，必须满足额外约束 #cf_span[t ≤ 5]。 ## Output 对于每个测试用例，输出一个整数，表示你为了使成功率等于你最喜欢的有理数所需做的最少提交次数；如果无法实现，则输出 _-1_。 [samples] ## Note 在第一个例子中，你需要再做 4 次成功提交。你的成功率将变为 #cf_span[7 / 14]，即 #cf_span[1 / 2]。在第二个例子中，你需要再做 2 次成功提交和 8 次失败提交。你的成功率将变为 #cf_span[9 / 24]，即 #cf_span[3 / 8]。在第三个例子中，无需做任何新提交。你的成功率已经是 #cf_span[20 / 70]，即 #cf_span[2 / 7]。在第四个例子中，唯一的失败提交破坏了你获得成功率为 1 的希望。

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $, let: - $ x_k, y_k \in \mathbb{Z}_{\geq 0} $ with $ 0 \leq x_k \leq y_k $, - $ p_k, q_k \in \mathbb{Z}_{\geq 0} $ with $ 0 \leq p_k \leq q_k $, $ q_k > 0 $, - $ \frac{p_k}{q_k} $ be an irreducible fraction. **Constraints** 1. $ 1 \leq t \leq 1000 $ 2. $ 0 \leq x_k \leq y_k \leq 10^9 $ 3. $ 0 \leq p_k \leq q_k \leq 10^9 $, $ q_k > 0 $ 4. $ \gcd(p_k, q_k) = 1 $ **Objective** Find the smallest non-negative integer $ d $ such that there exist non-negative integers $ a, b $ with: $$ x_k + a = p_k \cdot n, \quad y_k + a + b = q_k \cdot n $$ for some integer $ n \geq 1 $, and $ a \geq 0 $, $ b \geq 0 $, or output $ -1 $ if no such $ d = a + b $ exists. Equivalently, find the minimal $ d \geq 0 $ such that: $$ \exists n \in \mathbb{Z}^+, \quad x_k \leq p_k n, \quad y_k \leq q_k n, \quad p_k n - x_k \leq q_k n - y_k $$ and $ d = (q_k n - y_k) $. Alternatively, minimize $ d = q_k n - y_k $ over integers $ n \geq \max\left( \left\lceil \frac{x_k}{p_k} \right\rceil, \left\lceil \frac{y_k}{q_k} \right\rceil \right) $ (with $ p_k > 0 $), under the constraint $ p_k n - x_k \leq q_k n - y_k $, and if $ p_k = 0 $, then $ x_k = 0 $ must hold. If $ p_k = 0 $ and $ x_k > 0 $, output $ -1 $.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "C. Success Rate",
    "description": {
      "content": "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 rat",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF807C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 rat...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "你是一位经验丰富的 Codeforces 用户。今天你发现，在你于 Codeforces 上的活动中，你一共提交了 #cf_span[y] 次，其中 #cf_span[x] 次成功。因此，你在 Codeforces 上的当前成功率是 #cf_span[x / y]。\n\n你最喜欢的区间 #cf_span[[0;1]] 内的有理数是 #cf_span[p / q]。现在你想知道：为了让你的成功率变为 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let:  \n- $ x_k, y_k \\in \\mathbb{Z}_{\\geq 0} $ with $ 0 \\leq x_k \\leq y_k $,  \n- ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments