方針

\(A_{i,j}=\gcd(i,j)\) を出力することで、この問題に正解できます。

正当性

構築した行列が問題の条件を満たすことを示します。

まず、任意の \(i,j\) について \(1 \le \gcd(i,j) \le N\) であるため、すべての成分は \(1\) 以上 \(N\) 以下です。

次に、任意の \(K\ (1 \le K \le N)\) と、任意の \(K \times K\) の小正方形を考えます。

この小正方形が、行 \(r,r+1,\ldots,r+K-1\) と、列 \(c,c+1,\ldots,c+K-1\) からなるとします。

連続する \(K\) 個の整数の中には、\(K\) の倍数がちょうど \(1\) 個存在します。したがって、

• \(r,r+1,\ldots,r+K-1\) の中には、\(K\) の倍数である行番号がちょうど \(1\) 個存在します。
• \(c,c+1,\ldots,c+K-1\) の中には、\(K\) の倍数である列番号がちょうど \(1\) 個存在します。

よって、この小正方形の中には、\(K \mid i\) と \(K \mid j\) を同時に満たす位置 \((i,j)\) がちょうど \(1\) 個存在します。

一方、構築より \(A_{i,j}=\gcd(i,j)\) であるため、

\[ K \mid A_{i,j} \iff K \mid \gcd(i,j) \iff K \mid i \text{ かつ } K \mid j \]

が成り立ちます。

したがって、この \(K \times K\) の小正方形には、\(K\) の倍数である成分がちょうど \(1\) 個存在します。

以上より、構築した行列は問題の条件をすべて満たします。

計算量

各成分について \(\gcd(i,j)\) を計算します。

\(1\) 回の最大公約数の計算量を \(O(\log N)\) とすると、各テストケースの時間計算量は

\[ O(N^2 \log N) \]

です。

全テストケースについては

\[ O\left(\sum N^2 \log N\right) \]

です。