103726: [Atcoder]ABC372 G - Ax + By < C
Description
Score : $625$ points
Problem Statement
You are given three length-$N$ sequences of positive integers: $A=(A_1,A_2,\ldots,A_N)$, $B=(B_1,B_2,\ldots,B_N)$, and $C=(C_1,C_2,\ldots,C_N)$.
Find the number of pairs of positive integers $(x, y)$ that satisfy the following condition:
- $A_i \times x + B_i \times y < C_i$ for all $1 \leq i \leq N$.
It can be proved that the number of such pairs of non-negative integers satisfying the condition is finite.
You are given $T$ test cases, each of which should be solved.
Constraints
- $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$
- The sum of $N$ over all test cases is at most $2 \times 10^5$.
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, $\mathrm{case}_i$ refers to the $i$-th test case.
$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$
Each test case is given in the following format:
$N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$
Output
Print $T$ lines. The $i$-th line $(1 \leq i \leq T)$ should contain the answer for $\mathrm{case}_i$.
Sample Input 1
2 2 1 1 4 1 2 5 1 1 1 2
Sample Output 1
2 0
In the first query, there are two valid pairs of integers: $(x, y) = (1, 1), (1, 2)$. Thus, the first line should contain $2$.
In the second query, there are no valid pairs of integers. Thus, the second line should contain $0$.
Sample Input 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
Sample Output 2
660 995 140
Output
得分: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)$的数量:
- 对于所有$1 \leq i \leq N$,有$A_i \times x + B_i \times y < C_i$。
可以证明,满足该条件的非负整数对的数量是有限的。
你有$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), (1, 2)$。因此,第一行应包含$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