分数: 625 点
问题陈述
给你三个长度-N 正整数序列: A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N),和 C=(C_1,C_2,\ldots,C_N).
查找正整数对的数量 (x, y) 满足以下条件:
- A_i \times x + B_i \times y < C_i 对于所有人 1 \leq i \leq N.
可以证明满足条件的这种正整数对的个数是有限的。
你被给予 T 测试用例,每个测试用例都应该被解决。
约束
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i, B_i, C_i \leq 10^9
- 总和 N 所有测试用例最多 2 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出。在这里, \mathrm{case}_i 指的是 i- 第一个测试用例。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
输出
打印 T 行。的 i第行 (1 \leq i \leq T) 应包含以下问题的答案 \mathrm{case}_i.
样本输入 1
2 2 1 1 4 1 2 5 1 1 1 2
示例输出 1
2 0
在第一个测试用例中,有两个有效的整数对: (x, y) = (1, 1), (2,1)。因此,第一行应该包含 2.
在第二个测试用例中,没有有效的整数对。因此,第二行应该包含 0.
示例输入 2
3 7 138 16011 918976 5478 7748 499926 5234 17727 748589 1157 10511 643136 31200 3005 721285 28839 14469 798851 1933 5378 864127 9 17775 1665 386430 37001 863 922418 9756 4182 746671 12379 9106 807578 3984 4049 640539 25333 9869 780810 20372 7000 688738 16107 11974 827227 10779 10531 770510 5 4916 14132 460944 11856 45422 610561 56014 18216 825793 10363 6220 945356 37418 33866 851593
示例输出 2
660 995 140