题解：P11919 [PA 2025] 水族馆 / Akwarium

题意

给你一个正整数 $n$。

让你求出 $\sqrt {a^2+b^2+h^2}\le n$，的解的数量（$a$，$b$，$h$ 都是正整数。）

90 pts

暴力枚举。

第一层循环枚举 $n$，第二层枚举 $a$，第三层枚举 $b$，然后就可以计算出 $h$，判断是否满足条件即可。

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int k=3;k<=n;k++){
		for(int a=1;a<k;a++){
			for(int b=a;b<k;b++){
				if(k*k-a*a-b*b<=0)break;
				double h=k*k-a*a-b*b;
				if((int)sqrt(h)*(int)sqrt(h)==h)ans++;
			}
		}
	}
	cout<<ans;
	return 0;
}

时间复杂度 $O(n^3)$。

100 pts

如果 $\sqrt {a^2+b^2+h^2}\le n$，那么 $a^2+b^2+h^2\le n^2$（废话）。

考虑先枚举 $a^2+b^2$ 的值，然后枚举 $n^2-h^2$ 的值，如果存在 $a^2+b^2=n^2-h^2$，就计入答案。

#include<bits/stdc++.h>
using namespace std;
int n,ans,a[51451400];
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			a[i*i+j*j]++;
	for(int i=1;i<=n;i++) 
		for(int j=1;j<i;j++)
			if(i*i>j*j&&a[i*i-j*j])ans+=a[i*i-j*j];
	cout<<ans;
	return 0;
}