题目描述
求四个正整数的平方和;
用for循环来写,i的长度能写到sqrt(n)
而有四重循环即算法复杂度为最小为sqrt(n)sqrt(n)sqrt(n),即只枚举a,b,c;d在枚举完前三个之后自动出来了,相当暴力,但时间复杂度为O(nsqrt(n));
只能在n<=10000的时候不会卡时间
而这道题的数据为5000000;自能将复杂度降到O(n);
则为两重循环,循环长度为sqrt(n);自然就变为O(n)了
关于用hash来做:
是将cc+d*d的值储存起来,且保证其唯一性
所以与hash很像(但正常的hash用的值太大了)(所以叫做模拟hash)正常的hash会超;
样例
blablabla
算法1
(模拟hash) $O(n)$
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int a,b,c,d,n;
int book[5000010];//下标的范围一定要大,因为是两个比较大的数c*c+d*d(比a*a+b*b要大)
int main()
{
for(c=0;c*c<=n;c++)//先来遍历c和d保证了c和d比a,b要大
{
for(int d=c;d*d+c*c<=n;d++)//d从a开始,保证了a与b不会,b与a的重复,且保证了d大于等于c
{
int t=c*c+d*d;
if(book[t]==-1)
{
book[t]=c;//hash的操作,c*c+d*d这一情况储存且里面是c的值,在判断a,b,c,d能否做成四平方和时有用;
}
}
}
for(int a=0;a*a<=n;a++)
{
for(int b=a;b*b+a*a<=n;b++)
{
int t=n-a*a-b*b;
if(book[t]==-1)continue;//如果在当前a,b的情况下,c,d 没有值时,则跳过
else {
d=sqrt(t-book[t]);
printf("%d %d %d %d\n",a,b,book[t],d);
return 0;//如果找到了则直接结束,
}
}
}
return 0;
}
算法2
(二分) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla