求助！

黑莓掌 — Fri, 15 Jul 2011 02:37:00 GMT

　　　　　　　　进贡者的要求

时间限制:: 5000ms
内存限制:: 65536kB

描述

在你的帮助下，塔纳很快就消除了旅馆老板的烦恼。为了答谢塔纳，旅馆老板准备了丰盛的伦巴那晚餐和别具风味的自酿果子酒与塔纳一同享用。当然最主要的还是想听塔纳说说一路上的奇闻异事。
觥筹交错间，远处传来的叮叮当当的摇铃声越来越近，最后停在了旅店的门口。原来是一队远道而来的进贡者。他们想找一间超大的房间入住，可是他们奇特的要求难住了那些拥有更大旅店的老板们。
这些进贡者必须根据自己进贡的编号来选择床号。如果一位进贡者的编号是a，并且旅馆的超大房间里有0…k-1一共k张床，那么他就会选择a mod k（a对k取余数）号床作为他睡觉的地点。显然，2位进贡者不能睡在同一张床上。那么在知道这些进贡者的编号的前提下，老板要为他们准备一间卧室，安排床的个数够用就好，也就是说既能满足进贡者得要求，又得安排最少的床，因为每张床就算不睡人也是要交费用的啊。
这能难住塔纳吗？要看你的了。

输入

第1行是进贡者的人数n(1 <= n <= 500)；
第2行是这n位进贡者的编号Si(1 <= Si <= 1000)，用空格隔开。

输出

共一行，输出最少的床的数目。

样例输入

5
4 6 9 10 13

样例输出

提示

对于上面的样例。
显然，至少得有5张床，可是4%5==9%5；如果是6张床，那么4%6==10%6；如果是7张床，那么6%7==13%7；而8张床既可以安排下所有的5位进贡者，又满足最小的床位费要求。
【算法提示】
对于共有k张床的房间，编号a和b的两位进贡者。
如果a % k == b % k（就是说a和b会选择同一张床）；
那么(a – b)一定是k的整数倍，也一定是k的因子的倍数，即(a – b)的所有因子ki都满足(a % ki) == (b % ki)，都不能选。
举例：a = 3，b = 7；(a – b) => 4；
所以4的所有因子都不能选。
即床数为1，2，4时两人会选择到同一张床。

这道题我不会，哪位好心的哥哥姐姐帮帮忙＾＾＾

黑莓掌 2011-07-15 10:37 发表评论

C++博客-c++联盟

求助！