313 人解决,399 人已尝试。
363 份提交通过,共有 1909 份提交。
2.7 EMB 奖励。
单点时限: 1.0 sec
内存限制: 256 MB
QQ小方以前不会求最小公倍数,现在他会了,所以他急切的想教会你。
两个或多个整数公有的倍数叫做它们的公倍数,其中除 $0$ 以外最小的一个公倍数就叫做这几个整数的最小公倍数。
我们经常用质因数分解法来求最小公倍数:把每个数分别分解质因数,再把各数中的全部公有质因数提取出来连乘,所得的积就是这几个数的最大公约数。
单单讲给你听肯定是不够的,为了表现自己,QQ小方现在要考考你。
QQ小方自己刚刚做了一道题目:三个小朋友经常去图书馆,分别每隔 $3$ 天、 $2$ 天、 $5$ 天去图书馆借书,他们恰好在第一天的时候都去了图书馆,要让QQ小方求出他们最少过几天又会在同一天去图书馆。这个问题对已经会了最小公倍数的QQ小方来说很简单。
QQ小方决定将问题升级,QQ小方现在会召集一些小朋友,他们会分别间隔一定的天数规律地来到图书馆,而一旦某一天图书馆来了至少一个小朋友,QQ小方都会告诉你这天的日期。QQ小方会在第一天的时候召集所有人来到图书馆。他现在想知道,对于他给定的日期,他最少需要召唤多少小朋友。
QQ小方只会记录在 $2\cdot 10^5$ 以内出现小朋友的日期,也就是说,后续的日期你可以忽略不计。当然QQ小方也可以在任意时刻结束记录。
QQ小方的记录当然是不会出错的,也就是输入的数据保证存在合法的解。
输入数据第一行包含一个整数 $n(1\le n\le 2\cdot 10^5)$ ,表示有其中 $n$ 天是有人来的。
第二行包含 $n$ 个用空格分开的整数 $a_1,a_2,\cdots ,a_n(1= a_1< a_2< \cdots < a_n\le 2\cdot 10^5)$ ,表示 $n$ 个有人来的日期。
输出一行包含一个整数,表示需要的最少小朋友数量。
3 1 2 3
1
4 1 4 5 7
2
对于第一个样例,我们只需要一个小朋友,每天都来。
对于第二个样例,我们至少需要两个小朋友,分别间隔 $3$ 、 $4$ 天来。
313 人解决,399 人已尝试。
363 份提交通过,共有 1909 份提交。
2.7 EMB 奖励。
创建: 5 年,2 月前.
修改: 5 年,2 月前.
最后提交: 4 月,1 周前.
来源: N/A