bzoj1643 / P2666 [Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

时间:2022-10-30 16:28:35

[Usaco2007 Oct]Bessie's Secret Pasture 贝茜的秘密草坪

简单的dfs题

枚举前3个完全平方数,判断最后一个是不是完全平方数,统计合法方案数即可。

(zz选手竟把数据看成<=1e9)

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,ans;
void dfs(int t,int d){
if(d==){
int k=sqrt(t);
if(k*k==t) ++ans;
return ;
}
for(int i=;i*i<=t;++i)
dfs(t-i*i,d+);
}
int main(){
scanf("%d",&n);
dfs(n,);
printf("%d",ans);
return ;
}