NOIP_2009復(fù)賽試題—細(xì)胞分裂

1、細(xì)胞分裂題目分析版權(quán)所有 東華初級中學(xué)一、讀懂題意 Hanks 博士手里現(xiàn)在有N 種細(xì)胞，編號從1N，一個第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂為Si 個同種細(xì)胞（Si 為正整數(shù)）。 現(xiàn)在他需要選取某種細(xì)胞的一個放進(jìn)培養(yǎng)皿，讓其自由分裂，進(jìn)行培養(yǎng)。一段時間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入M 個試管，形成M 份樣本，用于實(shí)驗(yàn)。 試管數(shù)M 很大，普通的計(jì)算機(jī)的基本數(shù)據(jù)類型無法存儲這樣大的M 值，但萬幸的是，M 總可以表示為m1 的m2 次方，M = m1m2 ，其中m1，m2 均為基本數(shù)據(jù)類型可以存儲的正整數(shù)。版權(quán)所有 東華初級中學(xué)由此可知，對于任意一種細(xì)胞(si)，要想能夠用它來試驗(yàn)，必然存在k,

2、使得sik mod M =0對于任意一種細(xì)胞，期分裂的速度是指數(shù)形式增長的，如：1,si, si2, si3, si4,一、讀懂題意 注意，整個實(shí)驗(yàn)過程中不允許分割單個細(xì)胞，比如某個時刻若培養(yǎng)皿中有4 個細(xì)胞，Hanks 博士可以把它們分入2 個試管，每試管內(nèi)2 個，然后開始實(shí)驗(yàn)。但如果培養(yǎng)皿中有5個細(xì)胞，博士就無法將它們均分入2 個試管。此時，博士就只能等待一段時間，讓細(xì)胞們繼續(xù)分裂，使得其個數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。 為了能讓實(shí)驗(yàn)盡早開始，Hanks 博士在選定一種細(xì)胞開始培養(yǎng)后，總是在得到的細(xì)胞“剛好可以平均分入M 個試管”時停止細(xì)胞培養(yǎng)并開始實(shí)驗(yàn)。 現(xiàn)在博士希望知道，選擇

3、哪種細(xì)胞培養(yǎng)，可以使得實(shí)驗(yàn)的開始時間最早。版權(quán)所有 東華初級中學(xué)由此可知，對于任意一種細(xì)胞(si)，要想能夠盡早用它來試驗(yàn)，計(jì)算出使得sik mod M =0 的最小kmin值。枚舉每一種細(xì)胞，計(jì)算其kmin的值,其中最小的就是題目所求。輸入輸出【輸入】 輸入文件名為 cell.in，共有三行。 第一行有一個正整數(shù) N，代表細(xì)胞種數(shù)。 第二行有兩個正整數(shù) m1，m2，以一個空格隔開，m1m2即表示試管的總數(shù)M。 第三行有 N 個正整數(shù)，第i 個數(shù)Si 表示第i 種細(xì)胞經(jīng)過1 秒鐘可以分裂成同種細(xì)胞的個數(shù)?！据敵觥?輸出文件 cell.out 共一行，為一個整數(shù)，表示從開始培養(yǎng)細(xì)胞到實(shí)驗(yàn)?zāi)軌蜷_始

4、所經(jīng)過的最少時間（單位為秒）。如果無論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)-1。【數(shù)據(jù)范圍】 對于所有的數(shù)據(jù)，有1 N 10000，1 m1 30000，1 m2 10000，1 Si 2,000,000,000。 版權(quán)所有 東華初級中學(xué)【輸入輸出樣例 1】cell.in12 13cell.out -1【輸入輸出樣例1 說明】經(jīng)過 1 秒鐘，細(xì)胞分裂成3 個，經(jīng)過2 秒鐘，細(xì)胞分裂成9 個，可以看出無論怎么分裂，細(xì)胞的個數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入2 個試管。版權(quán)所有 東華初級中學(xué)只有一種細(xì)胞2個試管1個細(xì)胞1秒鐘可以分裂分裂成3個【輸入輸出樣例 2】cell.in 224

5、 130 12cell.out2【輸入輸出樣例2 說明】第 1 種細(xì)胞最早在3 秒后才能均分入24 個試管，而第2 種最早在2 秒后就可以均分（每試管144/(241)=6 個）。故實(shí)驗(yàn)最早可以在2 秒后開始。版權(quán)所有 東華初級中學(xué)細(xì)胞種類:2種試管數(shù)M:24個=2*2*2*3=23*3第1種細(xì)胞s1=30=2*3*5第2種細(xì)胞s2=12=2*2*3=22*3思考：如果s2=9,結(jié)果會怎樣？輸入樣例分析 又如：1210 1280版權(quán)所有 東華初級中學(xué)細(xì)胞種類:1種試管數(shù)M:70個=2*3*5*7第1種細(xì)胞s1=280=23*5*7第一個疑問 對于每種細(xì)胞，什么條件下才存在k ，使得sik mo

6、d M =0？版權(quán)所有 東華初級中學(xué)假設(shè)：M的算術(shù)分解式為p1a1*p2a2*p3a3*ptat，p1,p2,p3,pt為M的互不相同的質(zhì)因數(shù)；則使得使得sik mod M=0成立的條件是： p1,p2,p3,pt也是Si的質(zhì)因數(shù)。第2個疑問 對于每種細(xì)胞，如果它能夠用來做實(shí)驗(yàn)（ sik mod M =0 ），那么用它來做試驗(yàn)的最早開始時間t應(yīng)如何計(jì)算？版權(quán)所有 東華初級中學(xué)設(shè)：M的算術(shù)分解式為:p1a1*p2a2*p3a3*ptat，p1,p2,p3,pt為M的互不相同的質(zhì)因數(shù)；且p1,p2,p3,pt 在Si的算術(shù)分解式為的指數(shù)為b1,b2,b3,bt,則T=maxtt, 1it期中，若ai mod bi =0， 則令tt=ai div bi,否則令tt=ai div bi +1M的素?cái)?shù)分解過程t1:array1.30000 of longint;fillchar(t1,sizeof(t1),0);temp:=m1; for i:=2 to temp do begin while temp