http://codeforces.com/contest/980/problem/D

cf.cpp

#include<bits/stdc++.h>
using namespace std;

int a[5005];
int lt[5005];
int cnt;

int ans[5005];
int vis[5005];

bool isSquare(int x, int y)
{
	if (x==0 && y==0) return true;
	if (x==0 || y==0) return false;
	if (1ll*x*y<0) return false;
	long long z = sqrt(1ll*x*y)+1e-10;
	return z*z==1ll*x*y;
}

int main()
{
	memset(lt, -1, sizeof(lt));
	int n;
	scanf("%d", &n);
	for (int i=0; i<n; i++)  {
		scanf("%d", &a[i]);
		for (int j=0; j<i; j++) {
			if (isSquare(a[i], a[j])) {
				lt[i] = lt[j];
				break;
			}
		}
		if (lt[i]==-1) lt[i]=cnt++;
	}
	for (int i=0; i<n; i++) {
		memset(vis, 0, sizeof(vis));
		int th = 0;
		int zero = 0;
		for (int j=i;j<n;j++) {
			if (a[j]==0) zero=1;
			if (vis[lt[j]]==0) {
				th ++;
				vis[lt[j]] = 1;
			}
			if (zero) {
				ans[max(th-1, 1)] ++;
			}
			else {
				ans[th] ++;
			}
		}
	}
	for (int i=1; i<=n; i++) printf("%d ", ans[i]);
	return 0;
}