← 返回题目列表

AtCoder · abc372_g

G. 斧头 + 通过 < C

中文机器翻译题面 查看原题

分数: 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