解题思路

给定一个未知排列 $p=(p_1,\dots,p_n)$ （由 $1..n$ 的所有数恰好一次组成），用它构造矩阵

$G_{i,j}$ = $p_i$ $\times$ $p_j$ $(1\le i,j\le n)$

现在给出矩阵 $G$ ，需恢复排列 $p$ 。

关键观察：对任意一行 $i$ ，这一行所有元素的最大公约数为

题目内容

给定一个长度为 $n$ 的未知排列 $p$ ，小红使用它构造了一个 $n×n$ 的矩阵 $G$ ，满足：

对于所有 $1≤i,j≤n$ ，有 $G_{i,j}=p_i×p_j$ 。

现在，小红已经给出了矩阵 $G$ ，你能恢复排列 $p$ 吗。