P15737 [JAG 2024 Summer Camp #2] I Love Square Number

考虑一个具有 $\frac{N(N+1)}{2}$ 个顶点和 $\frac{3N(N-1)}{2}$ 条边的图，其中 $N$ 是一个大于等于 $2$ 的整数。 - 顶点集合为 $\{(i, j) \mid 1 \leq i \leq N, 1 \leq j \leq i\}$。 - 在 $(i, j)$ 与 $(i + 1, j)$ 之间存在一条权值为 $a_{i,j}$ 的边（对于 $1 \leq i \leq N - 1$ 且 $1 \leq j \leq i$）。 - 在 $(i, j)$ 与 $(i + 1, j + 1)$ 之间存在一条权值为 $b_{i,j}$ 的边（对于 $1 \leq i \leq N - 1$ 且 $1 \leq j \leq i$）。 - 在 $(i, j)$ 与 $(i, j + 1)$ 之间存在一条权值为 $c_{i,j}$ 的边（对于 $2 \leq i \leq N$ 且 $1 \leq j \leq i - 1$）。 对于该图中的一条简单路径，其路径的权值定义为该路径所经过的各条边的权值的**乘积**。 确定满足以下条件的无序顶点对 $\{s, t\}$（$s \neq t$）的数量：从 $s$ 到 $t$ 的任意简单路径的权值都是一个平方数。

输入以如下格式给出： $$ \begin{aligned} &N \\ &a_{1,1} \\ &a_{2,1} \ a_{2,2} \\ &\vdots \\ &a_{N-1,1} \ \cdots \ a_{N-1,N-1} \\ &b_{1,1} \\ &b_{2,1} \ b_{2,2} \\ &\vdots \\ &b_{N-1,1} \ \cdots \ b_{N-1,N-1} \\ &c_{2,1} \\ &c_{3,1} \ c_{3,2} \\ &\vdots \\ &c_{N,1} \ \cdots \ c_{N,N-1} \end{aligned} $$ - $2 \leq N \leq 1,000$ - $1 \leq a_{i,j}, b_{i,j}, c_{i,j} \leq 10^6$ - 所有输入值均为整数。

输出答案。

翻译由 DeepSeek V3.2 完成