← 返回题目列表

Codeforces · 963/C

C. 切割矩形

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

边长为 $$$A$$$ 和 $$$B$$$ 的矩形被切成多个矩形,切口平行于其边。例如,如果进行 $$$p$$$ 水平切割和 $$$q$$$ 垂直切割,则切割后会留下 $$$(p + 1) \cdot (q + 1)$$$ 矩形。切割后,矩形有$$$n$$$ 不同类型。如果一个矩形的至少一条边不等于另一个矩形的对应边,则两个矩形不同。请注意,矩形不能旋转,这意味着如果 $$$a \neq b$$$ ,则矩形 $$$a \times b$$$ 和 $$$b \times a$$$ 被视为不同。

对于每种类型的矩形,给出了矩形边的长度以及切割初始矩形后留下的该类型矩形的数量。

计算$$$(A; B)$$$对的数量,例如可以通过切割边长为$$$A$$$和$$$B$$$的矩形来创建给定的矩形。请注意,当 $$$A \neq B$$$ 时,$$$(A; B)$$$ 和 $$$(B; A)$$$ 被视为不同。

输入

第一行由一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^{5}$$$) 组成 - 切割初始矩形后剩下的不同类型矩形的数量。

接下来的 $$$n$$$ 行每行包含三个整数 $$$w_{i}, h_{i}, c_{i}$$$ $$$(1 \leq w_{i}, h_{i}, c_{i} \leq 10^{12})$$$ ——该类型矩形的边长和该类型矩形的数量。

保证不同类型的矩形是不同的。

输出

输出一个整数——问题的答案。

示例

输入 #1

1
1 1 9

输出 #1

3

输入 #2

2
2 3 20
2 4 40

输出 #2

6

输入 #3

2
1 2 5
2 3 5

输出 #3

0

注意

在第一个示例中,存在三个合适的对:$$$(1; 9)$$$、$$$(3; 3)$$$ 和 $$$(9; 1)$$$。

在第二个示例案例中,有 6 个合适的对:$$$(2; 220)$$$、$$$(4; 110)$$$、$$$(8; 55)$$$、$$$(10; 44)$$$、$$$(20; 22)$$$ 和 $$$(40; 11)$$$。

这里是 $$$(20; 22)$$$ 的切割样本。

第三个样本没有合适的对。