本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-05 18:49:32

（事先声明：这个方法是班里的大佬告诉我的）
看到这道题， 你是不是有点懵？

---------------------------------------------------------切入正题-------------------------------------------------------------

首先你要知道若 $x$ 是一个能被 $a^2$ 得到， 且 $a$ 为整数的， 它就是一个平方数。
且， 若 $x$ 为一个平方数， 那么 $100x$ 也为一个平方数。
为什么呢？
因为：
$$100x=a\times a\times 100$$ $$100x=a\times a\times (10\times 10)$$ $$100x=10a\times 10a$$ $$100x=(10a)^2$$ 这样做， 我们就可以得到 $n-2$ 个平方数。
接下来， 我们考虑把 $0$ 塞到中间去。
因为：
$$(a+b)^2=(a+b)(a+b)$$ $$(a+b)^2=a(a+b)+b(a+b)$$ $$(a+b)^2=a^2+ab+b^2+ab$$ $$(a+b)^2=a^2+2ab+b^2$$ 接下来， 我们拿 $169$ 试一试。
我们设 $a$ 为 $10$，$b$ 为 $3$：
$$(10+3)^2=10^2+2\times 10\times 3+3^2$$ $$(10+3)^2=100+60+9=169$$ 然后， 我们在 $1$ 后面塞一个 $0$，$9$ 前面塞一个 $0$。
这样，$a$ 就变成了 $100$，$b$ 不变。
得到：
$$(100+3)^2=100^2+2\times 100\times 3+3^2$$ $$(100+3)^2=10000+600+9=10609$$ 恰好等于 $10609$。
$961$ 同上，以此类推。
这样，我们得到了五位平方数：$16900$，$19600$，$96100$，$10609$，$90601$。
是不是很震惊？
代码如下：

#include<bits\/stdc++.h>
using namespace std;
string s[100][100],ss[50];
int t,n;
void workk(){\/\/预处理1 
	for(int i=1;i<=48;i++){
		ss[i]=ss[i-1]+"0";
	}
	return;
}
void work(){\/\/预处理2 
	s[1][1]="1";
	s[3][1]="169";
	s[3][2]="961";
	s[3][3]="196";
	for(int i=5;i<=99;i+=2){
		for(int j=1;j<=i-2;j++){
			s[i][j]=s[i-2][j]+"00";
		}
		s[i][i-1]="1"+ss[(i-3)>>1]+"6"+ss[(i-3)>>1]+"9";
		s[i][i]="9"+ss[(i-3)>>1]+"6"+ss[(i-3)>>1]+"1";
	}
}
int main(){
	cin>>t;
	workk();
	work();
	for(int i=1;i<=t;i++){
		cin>>n;
		for(int j=1;j<=n;j++){
			cout<<s[n][j]<<endl;\/\/直接输出 
		}
	}
	return 0;
}