AT_abc372_g [ABC372G] Ax + By < C

题目描述

题目简述

给定三个数列 $(A_1, A_2, \cdots, A_N)$，$(B_1, B_2, \cdots, B_N)$，$(C_1, C_2, \cdots, C_N)$，求满足 $A_ix+B_iy<C_i$ ($1 \leq i \leq N$) 的有序正整数对 $(x,y)$ 的个数。

输入格式

本题有多组测试数据。

第 $1$ 行输入一个正整数 $T$，表示数据组数。

接下来每个数据组：第 $1$ 行输入一个正整数 $N$，接下来 $N$ 行每行输入三个正整数 $A_i, B_i, C_i$。

输出格式

对于每个数据组，输出一个整数表示答案。

输入输出样例 #1

输入 #1

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

输出 #1

2
0

输入输出样例 #2

输入 #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

说明/提示

约定 $1 \leq T \leq 2\times 10^5$，$1 \leq \sum N \leq 2\times 10^5$，$1 \leq A_i, B_i, C_i \leq 10^9$。

对于样例 $1$，第一个数据组中满足条件的 $(x, y)$ 有 $(1, 1)$ 和 $(2, 1)$，故应当输出 $2$。第二个数据组中，没有满足条件的 $(x, y)$，故应当输出 $0$。