CF1916D Mathematical Problem 讲解
zrl123456
·
·
题解
（事先声明：这个方法是班里的大佬告诉我的）
看到这道题， 你是不是有点懵？
---------------------------------------------------------切入正题-------------------------------------------------------------
首先你要知道若 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。
这样，我们得到了五位平方数：$16900$，$19600$，$96100$，$10609$，$90601$。
是不是很震惊？
代码如下：
```cpp
#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;
}
```