進貢者的要求
時間限制:
5000ms
內(nèi)存限制:
65536kB
描述
在你的幫助下，塔納很快就消除了旅館老板的煩惱。為了答謝塔納，旅館老板準備了豐盛的倫巴那晚餐和別具風味的自釀果子酒與塔納一同享用。當然最主要的還是想聽塔納說說一路上的奇聞異事。
觥籌交錯間，遠處傳來的叮叮當當?shù)膿u鈴聲越來越近，最后停在了旅店的門口。原來是一隊遠道而來的進貢者。他們想找一間超大的房間入住，可是他們奇特的要求難住了那些擁有更大旅店的老板們。
這些進貢者必須根據(jù)自己進貢的編號來選擇床號。如果一位進貢者的編號是a，并且旅館的超大房間里有0…k-1一共k張床，那么他就會選擇a mod k（a對k取余數(shù)）號床作為他睡覺的地點。顯然，2位進貢者不能睡在同一張床上。那么在知道這些進貢者的編號的前提下，老板要為他們準備一間臥室，安排床的個數(shù)夠用就好，也就是說既能滿足進貢者得要求，又得安排最少的床，因為每張床就算不睡人也是要交費用的啊。
這能難住塔納嗎？要看你的了。
輸入
第1行是進貢者的人數(shù)n(1 <= n <= 500)；
第2行是這n位進貢者的編號Si(1 <= Si <= 1000)，用空格隔開。
輸出
共一行，輸出最少的床的數(shù)目。
樣例輸入 
5
4 6 9 10 13
樣例輸出 
8
提示
對于上面的樣例。
顯然，至少得有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的整數(shù)倍，也一定是k的因子的倍數(shù)，即(a – b)的所有因子ki都滿足(a % ki) == (b % ki)，都不能選。
舉例：a = 3，b = 7；(a – b) => 4；
所以4的所有因子都不能選。
即床數(shù)為1，2，4時兩人會選擇到同一張床。
 
 
這道題我不會，哪位好心的哥哥姐姐幫幫忙＾＾＾