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