[R17C]投票分组2 - 代码源竞赛平台

时空限制

1S/512M

题目描述

班上有 $n$ 名同学，同学的编号为 $1\sim n$。

现在需要通过投票确定班服的款式，有款式 $1$ 和款式 $2$ 两个选项，已知同学 $i$ 支持款式 $a_i$。

投票的规则为：

• 先将同学按编号每 $k$ 个分为一组，要求 $k$ 是 $n$ 的因数，即同学 $1\sim k$ 为第 $1$ 组，同学 $k+1\sim 2\times k$ 为第 $2$ 组，以此类推；
• 每个同学投出一票支持款式 $1$ 或者款式 $2$；
• 每个小组统计组内同学的投票情况，如果本小组中支持款式 $1$ 的票多于支持款式 $2$ 的票，那么视为整个小组支持款式 $1$。

对于 $n$ 的每个因数 $k$，按 $k$ 从小到大的顺序，分别求将同学按编号每 $k$ 个分为一组后有多少个小组支持款式 $1$。

格式

输入格式

第一行包含一个整数 $n$，表示同学的数量。

第二行包含 $n$ 个整数 $a_i$，分别表示每个同学支持哪个款式。

输出格式

对于 $n$ 的每个因数 $k$，按 $k$ 从小到大的顺序，在单独的一行中输出一个整数，表示将同学按编号每 $k$ 个分为一组后支持款式 $1$ 的小组的数量。

样例

样例输入 #1

12
1 2 2 1 1 2 1 1 2 2 1 2

样例输出 #1

6
1
2
1
0
0

样例解释 #1

如果每个小组 $1$ 个同学，共有 $12$ 个小组，其中有 $6$ 个小组支持款式 $1$：$1,4,5,7,8,11$。

如果每个小组 $2$ 个同学，共有 $6$ 个小组，其中有 $1$ 个小组支持款式 $1$：$4$。

如果每个小组 $3$ 个同学，共有 $4$ 个小组，其中有 $2$ 个小组支持款式 $1$：$2,3$。

如果每个小组 $4$ 个同学，共有 $3$ 个小组，其中有 $1$ 个小组支持款式 $1$：$2$。

如果每个小组 $6$ 个同学，共有 $2$ 个小组，其中有 $0$ 个小组支持款式 $1$。

如果每个小组 $12$ 个同学，共有 $1$ 个小组，其中有 $0$ 个小组支持款式 $1$。

数据规模

对于 $50\%$ 的数据，$n\leq 1000$。

对于 $100\%$ 的数据，$1\leq n\leq 10^5$，$1\leq a_i\leq 2$。