二分：四平方和

• 第七届蓝桥杯省赛C++A/B组
• • • 题意
    • 思路1
    • 代码
    • 思路2
    • 代码
    • 坑点
    • 总结

输入一个整数n
输出至少4个数使得这四个数那个数的平方和为n。零也是可以的。

• 1.纯暴力的思想就是先算出第一个数，第二个数，第三个数，然后在用n减第一个，第二个，第三个数的平方和，开根号求得第四个数的和。（原题会AC，但是ACwing可能会超时。）

#include 
#include
#include
#include
using namespace std;
int main()
{
	int n;
	cin>>n;
	for(int a=0;a*a<=n;a++)//a表示第个数的值， 
	{
		for(int b=a;a*a+b*b<=n;b++)//b表示第二个数， 
		{
			for(int c=b;a*a+b*b+c*c<=n;c++)
			{
				int t=n-a*a-b*b-c*c;//表示第四个数平方的值。
				int d=sqrt(t);
				if(d*d==t)//当d*d等于t的适合，则表示当前有解。
				{
					cout< 
思路2 
 
 
1.使用二分求答案思路的话和上面纯暴力差不多。
 
 
代码 
#include
#include 
#include
#include
using namespace std;
const int N=2500010;//范围。 
struct sum
{
	int s;//表示c和d的平方的和。 
	int c;
	int d;
	bool operator < (const sum &t)const
	{
		if(s!=t.s) return s>n;
	for(int c=0;c*c<=n;c++)
	{
		for(int d=c;c*c+d*d<=n;d++)
		{
			sum[m++]={c*c+d*d,c,d};//c*c+d*d表示上面结构体函数当中的s。m++表示小标加一。 
		}
	 } 
	 sort(sum,sum+m);
	 for(int a=0;a*a<=n;a++)//第一个数 
	 {
	 	for(int b=0;a*a+b*b<=n;b++)//第二个数 
	 	{
	 		int t=n-a*a-b*b;//t表示cd的平方和。
			int l = 0;
			int r = m-1;
			while(l=t) r = mid;//sum[mid].s表示上面结构体 的s 这个二分做的就是 读取的数组当如果有一个s等于t时候，当前a,b是有解的。 
				else l = mid +1;
			}
			if(sum[l].s==t)
			{
				cout< 
坑点 
 
 
1.时间复杂的注意。
 
 
总结 
 
 
二分。