C. Cutting Rectangle

一个边长为 $A$ 和 $B$ 的矩形被平行于其边的切割线分割成若干小矩形。例如，若进行了 $p$ 条水平切割和 $q$ 条垂直切割，则切割后剩余 $(p + 1) \dot.op (q + 1)$ 个矩形。切割后，得到了 $n$ 种不同类型的矩形。两个矩形不同，当且仅当至少有一个矩形的某一边长不等于另一个矩形对应的边长。注意，矩形不能旋转，这意味着 $a \times b$ 和 $b \times a$ 被视为不同矩形，当 $a \ne b$ 时。 对于每种类型的矩形，给出了该类型矩形的边长以及切割后剩余的该类型矩形的数量。 计算满足条件的有序对 $(A, B)$ 的数量，使得可以通过切割一个边长为 $A$ 和 $B$ 的矩形得到给定的所有矩形。注意，当 $A \ne B$ 时，$(A, B)$ 和 $(B, A)$ 被视为不同的对。 第一行包含一个整数 $n$ ($1 \le n \le 2 \dot.op 10^5$) —— 切割后剩余的不同类型矩形的数量。 接下来的 $n$ 行，每行包含三个整数 $w_i, h_i, c_i$ ($1 \le w_i, h_i, c_i \le 10^{12}$) —— 表示该类型矩形的边长及该类型矩形的数量。 保证不同类型的矩形互不相同。 输出一个整数 —— 问题的答案。 在第一个样例中，有三个满足条件的对：$(1, 9)$、$(3, 3)$ 和 $(9, 1)$。 在第二个样例中，有六个满足条件的对：$(2, 220)$、$(4, 110)$、$(8, 55)$、$(10, 44)$、$(20, 22)$ 和 $(40, 11)$。 下图展示了 $(20, 22)$ 的切割示例。 第三个样例没有满足条件的对。 ## Input 第一行包含一个整数 $n$ ($1 \le n \le 2 \dot.op 10^5$) —— 切割后剩余的不同类型矩形的数量。接下来的 $n$ 行，每行包含三个整数 $w_i, h_i, c_i$ ($1 \le w_i, h_i, c_i \le 10^{12}$) —— 表示该类型矩形的边长及该类型矩形的数量。保证不同类型的矩形互不相同。 ## Output 输出一个整数 —— 问题的答案。 [samples] ## Note 在第一个样例中，有三个满足条件的对：$(1, 9)$、$(3, 3)$ 和 $(9, 1)$。在第二个样例中，有六个满足条件的对：$(2, 220)$、$(4, 110)$、$(8, 55)$、$(10, 44)$、$(20, 22)$ 和 $(40, 11)$。下图展示了 $(20, 22)$ 的切割示例。第三个样例没有满足条件的对。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of distinct rectangle types. For each $ i \in \{1, \dots, n\} $, let $ (w_i, h_i, c_i) \in \mathbb{Z}^+ \times \mathbb{Z}^+ \times \mathbb{Z}^+ $ denote the width, height, and count of rectangles of type $ i $. Let $ \mathcal{R} = \{ (w_i, h_i, c_i) \mid i = 1, \dots, n \} $ be the set of rectangle types. Let $ A, B \in \mathbb{Z}^+ $ be the dimensions of the original rectangle. **Constraints** 1. All $ w_i, h_i, c_i \geq 1 $, and $ c_i \leq 10^{12} $, $ n \leq 2 \cdot 10^5 $. 2. All rectangle types are distinct: $ (w_i, h_i) \neq (w_j, h_j) $ for $ i \neq j $. 3. The original rectangle is partitioned into a grid of smaller rectangles via axis-aligned cuts: - There exist integers $ p, q \geq 0 $ such that the grid has $ (p+1) \times (q+1) $ cells. - Each small rectangle has width $ w $ from a multiset $ W = \{w_1, \dots, w_{p+1}\} $ and height $ h $ from a multiset $ H = \{h_1, \dots, h_{q+1}\} $, such that: $$ A = \sum_{j=1}^{p+1} w_j, \quad B = \sum_{k=1}^{q+1} h_k $$ - The multiset of resulting rectangles is exactly $ \{ (w_j, h_k) \mid j \in [p+1], k \in [q+1] \} $, with multiplicities $ c_{(w_j, h_k)} = 1 $ for each cell, but in our input, each distinct $ (w_i, h_i) $ appears $ c_i $ times. 4. The multiset of small rectangles must match the input: for each type $ (w_i, h_i) $, the number of times it appears in the grid is exactly $ c_i $. That is, if we define a bipartite grid with row widths $ W $ and column heights $ H $, then: $$ \forall i, \quad c_i = |\{ (j,k) \mid w_j = w_i \text{ and } h_k = h_i \}| $$ **Objective** Count the number of ordered pairs $ (A, B) \in \mathbb{Z}^+ \times \mathbb{Z}^+ $ such that there exist multisets $ W = \{w_1, \dots, w_m\} $, $ H = \{h_1, \dots, h_n\} $ satisfying: - $ A = \sum_{w \in W} w $, - $ B = \sum_{h \in H} h $, - The multiset $ \{ (w, h) \mid w \in W, h \in H \} $ equals the multiset $ \bigcup_{i=1}^n \{ (w_i, h_i) \} \times c_i $. Equivalently, define a matrix $ C \in \mathbb{Z}_{\geq 0}^{U \times V} $, where $ U $ is the set of distinct widths, $ V $ the set of distinct heights, and $ C_{w,h} = c_i $ if $ (w,h) = (w_i,h_i) $, else 0. Then $ (A,B) $ is valid iff there exist vectors $ \mathbf{r} \in \mathbb{Z}_{\geq 0}^U $, $ \mathbf{c} \in \mathbb{Z}_{\geq 0}^V $ such that: - $ \sum_{u \in U} r_u \cdot \mathbf{1}_{u = w} = \text{multiplicity of } w \text{ in } W $, - $ \sum_{v \in V} c_v \cdot \mathbf{1}_{v = h} = \text{multiplicity of } h \text{ in } H $, - $ r_u \cdot c_v = C_{u,v} $ for all $ u \in U, v \in V $. Thus, the problem reduces to: **Count the number of ordered pairs $ (A, B) $** such that there exists a **rank-1 nonnegative integer matrix** $ R \odot C^T $ (outer product) matching the given $ C $, where $ R_{u,v} = r_u \cdot c_v = C_{u,v} $, and $$ A = \sum_{u \in U} r_u \cdot u, \quad B = \sum_{v \in V} c_v \cdot v $$ **Final Formal Statement** Let $ U = \{ w_i \mid i=1,\dots,n \} $, $ V = \{ h_i \mid i=1,\dots,n \} $. Define a matrix $ C: U \times V \to \mathbb{Z}_{\geq 0} $ by $ C(w,h) = c_i $ if $ (w,h) = (w_i,h_i) $, else $ 0 $. A pair $ (A,B) $ is valid iff there exist functions $ r: U \to \mathbb{Z}^+ $, $ c: V \to \mathbb{Z}^+ $ such that: $$ \forall w \in U, \; \forall h \in V, \quad r(w) \cdot c(h) = C(w,h) $$ and $$ A = \sum_{w \in U} r(w) \cdot w, \quad B = \sum_{h \in V} c(h) \cdot h $$ **Objective**: Count the number of such ordered pairs $ (A, B) $.