3663: 分配小组-训练套题T18T4

第四题：分配小组（poset.pas/in/out）

【问题描述】

有N个mars人想要进行一项活动，他们需要分成几个小组，每个人属于其中的一个小组。Mars人从出生起每个人就有一个印记，这个印记是个正整数。如果B的印记是A的倍数，那么B就是A的父亲。与地球人的定义不同，一个mars人可以有多个父亲。特别的，A不是自己的父亲，但是所有其他与A的印记相同的人都是A的父亲。因此，除了A自己，A的父亲的父亲都是A的父亲。

Mars人十分强调子女的独立，因此进行这项活动的分组时，任何人都不能和自己的父亲分到一个小组。你的任务就是对于给定的N个mars人，给出一种分组方案，使得小组的数量最少。显然，这个问题一定存在可行解。如果有多解，任意输出一组即可。

【输入文件】

第一行：一个整数N，表示mars人的数量

接下来一行有N个正整数，表示每个mars人的印记。

【输出文件】

一行，一个整数K，表示你分成的小组数量。

【样例输入】

5

1 1 3 1 5

【样例输出】

4

【数据范围】

N<=5000

1<=所有的印记<=5000