P1586 题解
a16_
·
·
个人记录
暴力
由于 n 很小，所以可以想到用 O(n^2) 的时间枚举四个数，卡卡常，或者开 O_2，可以水过去
于是大致有这样一份代码
while(T--){
scanf("%d",&n);
cnt=0;
e=sqrt(n);
for(int i1=0;i1<=e;i1++)
for(int i2=i1;i2<=e;i2++)
for(int i3=i2;i3<=e;i3++)
for(int i4=i3;i4<=e;i4++)
if(i1*i1+i2*i2+i3*i3+i4*i4==n)
cnt++;
printf("%d\n",cnt);
}
优化
题目要求 n=i_1^2+i_2^2+i_3^2+i_4^2(n,i1,i2,i3,i4\in N)
为了避免重复我们规定 0\le i_1\le i_2 \le i_3 \le i_4 \le \sqrt n
如果已知 i_1,i_2,i_3，那么再去枚举 i_4 是否会显得很 silly ？
我们可以判断 i_4=\sqrt{n-i_1^2-i_2^2-i_3^2} 是否合法
可以打表一下，直接判断，于是省去了一重循环
三重循环，复杂度为 $O(Tn\sqrt n)$，是对的了,加上一些剪枝，卡卡常，快得飞起
代码
```cpp
代码中 f[i]=i^2，减少计算量，
ps[n]=sqrt(n)，当然仅限 n 是完全平方数，因为不是整数的话没有意义
#include<cstdio>
int f[200];
int ps[40010];
int main(){
int T,n,cnt;
for(int i=0;i<=181;i++){
f[i]=i*i;
ps[f[i]]=i;
}
scanf("%d",&T);
while(T--){
scanf("%d",&n);
cnt=0;
for(register int i1=0;i1<=181;i1++){
if(f[i1]>n) break;
for(register int i2=i1;i2<=181;i2++){
if(f[i1]+f[i2]>n) break;
for(register int i3=i2;i3<=181;i3++){
int t=n-f[i1]-f[i2]-f[i3];
if(t<0) break;
if(ps[t]>=i3&&ps[t]) cnt++;
}
}
}
printf("%d\n",cnt);
}
return 0;
}
```
提交记录（O2与无O2）
