Problem D: P7023 [NWRRC 2017] Equal Numbers

# P7023 [NWRRC 2017] Equal Numbers

## 题目描述

给定一个包含 $n$ 个整数 $a_{1} \ldots a_{n}$ 的列表。你可以执行以下操作：选择某个 $a_{i}$ 并将其乘以任意正整数。  

你的任务是计算在进行 $k$ 次操作后列表中可能出现的不同整数的最小数量，要求对所有 $0 \le k \le n$ 都进行计算。

## 输入格式

输入的第一行包含一个整数 $n (1 \le n \le 3 \times 10^{5})$。输入的第二行包含 $n$ 个整数 $a_{i} (1 \le a_{i} \le 10^{6})$。

## 输出格式

输出一行包含 $n + 1$ 个整数。第 $i$ 个整数应为在进行 $i - 1$ 次操作后列表中可能的不同整数的最小数量。

## 输入输出样例 #1

### 输入 #1

```
6
3 4 1 2 1 2
```

### 输出 #1

```
4 4 3 3 2 2 1
```

## 说明/提示

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。