CF980D Perfect Groups

SaMer 为他的一个问题编写了有史以来最棒的测试用例。对于给定的一个整数数组，问题要求将数组划分为最少数量的组，使得同一组内任意两个整数的乘积都是完全平方数。 每个整数必须恰好属于一个组。然而，同一组内的整数在数组中不一定是连续的。 SaMer 希望利用已有的测试用例生成更多的测试用例。他的测试用例包含一个长度为 $n$ 的整数数组 $A$，他需要统计 $A$ 的所有连续子数组中，答案等于 $k$ 的子数组个数，其中 $k$ 为 $1$ 到 $n$（包含 $1$ 和 $n$）之间的每一个整数。

第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^8 \leq a_i \leq 10^8$），表示数组的元素。

输出 $n$ 个用空格分隔的整数，第 $k$ 个整数表示答案等于 $k$ 的连续子数组的个数。

由 ChatGPT 4.1 翻译