#P13514. [ABC372G] Ax + By < C

    ID: 12698 传统题 3000ms 1024MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2600提高+/省选-直线上包络单调栈类欧几里得算法有理数精确运算向下取整与向上取整

[ABC372G] Ax + By < C

AT_abc372_g [ABC372G] Ax + By < C

时间限制3.00s 内存限制1.00GB

题目描述

题目简述

给定三个数列 (A1,A2,⋯ ,AN)(A_1, A_2, \cdots, A_N),(B1,B2,⋯ ,BN)(B_1, B_2, \cdots, B_N),(C1,C2,⋯ ,CN)(C_1, C_2, \cdots, C_N),求满足 Aix+Biy<CiA_ix+B_iy<C_i (1≤i≤N1 \leq i \leq N) 的有序正整数对 (x,y)(x,y) 的个数。

输入格式

本题有多组测试数据。

第 11 行输入一个正整数 TT,表示数据组数。

接下来每个数据组:第 11 行输入一个正整数 NN,接下来 NN 行每行输入三个正整数 Ai,Bi,CiA_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≤T≤2×1051 \leq T \leq 2\times 10^5,1≤∑N≤2×1051 \leq \sum N \leq 2\times 10^5,1≤Ai,Bi,Ci≤1091 \leq A_i, B_i, C_i \leq 10^9。

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