Counting Square Numbers
wqh 给了 wtr1 一个长度为 n 的数组 A。对于 i=1,2,…,n，需要 wtr1 给出包含了位置 i 且区间和为完全平方数的子数组个数。由于最近 wtr1 很忙，请聪明的你帮帮他吧！若一个数是一个整数的平方，则称这个数是完全平方数。原数组中某段下标连续的元素按原顺序构成的数组称为子数组。
#include<bits/stdc++.h>
using namespace std;
#define N 5010
long long s[N];//原数组的前缀和
long long ans[N];//答案的差分数组
int main()
{
int n,a;
scanf("%d",&n);
s[0] = 0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
s[i] = s[i-1] + a;
}
for(int i=1;i<=n;i++)
{
for(int j=i;j<=n;j++)
{
//判断s[i,j]是不是完全平方数
long long sij = s[j] - s[i-1];
long long t = sqrt(sij);
if(t*t==sij)
{
ans[i] ++;
ans[j+1] --;
}
}
}
long long sum = 0;
for(int i=1;i<=n;i++)
{
sum += ans[i];
printf("%lld\n",sum);
}
return 0;
}