Cutting Rectangle

题意翻译

### 题目描述 一个 $A \times B$ 的矩形被与它相交的两条边分别平行的直线切割：如果被横着切了 $p$ 下，竖着切了 $q$ 下，那么切完后将会得到 $(p + 1) \cdot (q + 1)$ 个矩形。 切完后，这些矩形被分成了 $n$ 类。我们规定，对于两个矩形而言，如果一个矩形的至少有一条边不等于另一个矩形的对应边，则认为这两个矩形不同。**需要注意的是矩形不能旋转**，这意味着 $a \times b$ 的矩形和 $b \times a$ 的矩形是不同的（如果有 $a \ne b$）。（注：否则它们就是相同的，属于同一类） 对每一类矩形，给定这类矩形的长宽以及数量。计算有多少个二元组 $(A, B)$ 对应的矩形 $A \times B$ 可以切出给定的这些矩形。注意，如果 $A \ne B$，那么我们认为 $(A, B)$ 与 $(B, A)$ 是不同的。 ### 输入 第一行包含一个整数 $n \pod {1 \le n \le 2 \cdot 10^5}$，表示原矩形被切割后被分成的种类。 接下来 $n$ 行每行三个整数 $w_i, h_i, c_i \pod {1 \le w_i, h_i, c_i \le 10^{12}}$，表示第 $i$ 种矩形的长宽以及这种矩形的数量。保证不同种类的矩形长宽不完全相同。 ### 输出 输出一行一个整数表示答案。

题目描述

A rectangle with sides $ A $ and $ B $ is cut into rectangles with cuts parallel to its sides. For example, if $ p $ horizontal and $ q $ vertical cuts were made, $ (p + 1) \cdot (q + 1) $ rectangles were left after the cutting. After the cutting, rectangles were of $ n $ different types. Two rectangles are different if at least one side of one rectangle isn't equal to the corresponding side of the other. Note that the rectangle can't be rotated, this means that rectangles $ a \times b $ and $ b \times a $ are considered different if $ a \neq b $ . For each type of rectangles, lengths of the sides of rectangles are given along with the amount of the rectangles of this type that were left after cutting the initial rectangle. Calculate the amount of pairs $ (A; B) $ such as the given rectangles could be created by cutting the rectangle with sides of lengths $ A $ and $ B $ . Note that pairs $ (A; B) $ and $ (B; A) $ are considered different when $ A \neq B $ .

输入输出格式

输入格式

The first line consists of a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^{5} $ ) — amount of different types of rectangles left after cutting the initial rectangle. The next $ n $ lines each consist of three integers $ w_{i}, h_{i}, c_{i} $ $ (1 \leq w_{i}, h_{i}, c_{i} \leq 10^{12}) $ — the lengths of the sides of the rectangles of this type and the amount of the rectangles of this type. It is guaranteed that the rectangles of the different types are different.

输出格式

Output one integer — the answer to the problem.

输入输出样例

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

说明

In the first sample there are three suitable pairs: $ (1; 9) $ , $ (3; 3) $ and $ (9; 1) $ . In the second sample case there are 6 suitable pairs: $ (2; 220) $ , $ (4; 110) $ , $ (8; 55) $ , $ (10; 44) $ , $ (20; 22) $ and $ (40; 11) $ . Here the sample of cut for $ (20; 22) $ . The third sample has no suitable pairs.