Ax + By < C

题目描述

你被给出三个长度为 $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 &lt; C_i 对所有 $1 \leq i \leq N$ 成立。

可以证明满足条件的正整数对的个数是有限的。
给出 $T$ 个测试用例，每个测试用例都应被解决。

输入格式

输入从标准输入按以下格式给出。这里，$\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$ 的答案。

2
2
1 1 4
1 2 5
1
1 1 2

2
0

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

660
995
140

提示

$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$。
所有输入值均为整数。在第一个测试用例中，有两个合法的整数对：$(x, y) = (1, 1), (2,1)$。因此，第一行应包含 $2$。
在第二个测试用例中，没有合法的整数对。因此，第二行应包含 $0$。

标签: AtCoder|abc372G

来源

AtCoder|abc372G