3723. 最小公倍数

单点时限: 1.0 sec

内存限制: 256 MB

QQ小方以前不会求最小公倍数,现在他会了,所以他急切的想教会你。

两个或多个整数公有的倍数叫做它们的公倍数,其中除 以外最小的一个公倍数就叫做这几个整数的最小公倍数。

我们经常用质因数分解法来求最小公倍数:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。

单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。

QQ小方自己刚刚做了一道题目:三个小朋友经常去图书馆,分别每隔 天、 天、 天去图书馆借书,他们恰好在第一天的时候都去了图书馆,要让QQ小方求出他们最少过几天又会在同一天去图书馆。这个问题对已经会了最小公倍数的QQ小方来说很简单。

QQ小方决定将问题升级,QQ小方现在会召集一些小朋友,他们会分别间隔一定的天数规律地来到图书馆,而一旦某一天图书馆来了至少一个小朋友,QQ小方都会告诉你这天的日期。QQ小方会在第一天的时候召集所有人来到图书馆。他现在想知道,对于他给定的日期,他最少需要召唤多少小朋友。

QQ小方只会记录在 以内出现小朋友的日期,也就是说,后续的日期你可以忽略不计。当然QQ小方也可以在任意时刻结束记录。

QQ小方的记录当然是不会出错的,也就是输入的数据保证存在合法的解。

输入格式

输入数据第一行包含一个整数 ,表示有其中 天是有人来的。

第二行包含 个用空格分开的整数 ,表示 个有人来的日期。

输出格式

输出一行包含一个整数,表示需要的最少小朋友数量。

样例

Input
3
1 2 3
Output
1
Input
4
1 4 5 7
Output
2

提示

样例解释

对于第一个样例,我们只需要一个小朋友,每天都来。

对于第二个样例,我们至少需要两个小朋友,分别间隔 天来。

252 人解决,322 人已尝试。

293 份提交通过,共有 1475 份提交。

2.9 EMB 奖励。

创建: 2 月,3 周前.

修改: 2 月,3 周前.

最后提交: 6 天,18 小时前.

来源: N/A

题目标签