【枚举】bzoj1643 [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

2024-09-27 23:19:28

显然<=n的平方数只有sqrt(n)个，三重循环枚举三块草坪，再减一下验证最后一块是不是平方数。O(n*sqrt(n))。

#include<cstdio>

#include<cmath>

using namespace std;

int n,ans;

int sqr(int x){return x*x;}

int main()

{

	scanf("%d",&n);

	for(int i=0;i*i<=n;++i)

	  for(int j=0;j*j+i*i<=n;++j)

	    for(int k=0;k*k+i*i+j*j<=n;++k)

	      {

	      	int t=n-i*i-j*j-k*k;

	      	if(sqr((int)sqrt((double)t))==t)

	      	  ++ans;

	      }

	printf("%d\n",ans);

	return 0;

}

最新文章

热门文章