[洛谷]P1586 四方定理

算法标签

题目简叙

思路

代码

#include<iostream>

using namespace std;

const int N=32768;
bool st[N+10];

int main()
{
    int t,n;
    cin>>t;
    
    for(int i=0;i*i<=N;i++)if(!st[i*i])st[i*i]=true;
    while(t--)
    {
        int cnt=0;
        cin>>n;
        
        for(int a=0;a*a<n;a++)
            for(int b=0;b*b+a*a<n;b++)
                for(int c=0;c*c+b*b+a*a<n;c++)  
                    {
                        int d = n-a*a-b*b-c*c;
                        if(!st[d])continue;//不是平方数
                        if(a*a<=b*b&&a*a<=c*c&&c*c<=d)//ABCD都不相等
                            if(b*b<=c*c&&b*b<=d)
                                if(c*c<=d)
                                    cnt++;
                    }
        cout<<cnt<<endl;            
    }
    
    return 0;
}

AC记录