提交时间:2024-11-28 13:13:16
运行 ID: 35145
#include<bits/stdc++.h> #define int long long using namespace std; const int maxn=5e6+7; int n,k; int dp[2][maxn]; inline void sub2(){ dp[0][0]=1; for(int i=1;i<=3;i++){ int f=i&1; memset(dp[f],0,sizeof(dp[f])); for(int t=1;t<=n;t++){ for(int j=t*t;j<=n*n+k;j++)dp[f][j]+=dp[f^1][j-t*t]; } } int ans=0; for(int i=1;i<=n;i++)ans+=dp[1][i*i+k]; cout<<ans<<endl; return; } int C[maxn]; signed main(){ cin>>n>>k; if(n<=400){sub2();return 0;} for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ C[i*i+j*j]++; } } int ans=0; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int p=i*i-j*j+k; if(p<0)continue; ans+=C[p]; } } cout<<ans<<endl; }