題目描述

Hanks 博士是 BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家。現(xiàn)在，他正在為一個(gè)細(xì)胞實(shí)

驗(yàn)做準(zhǔn)備工作：培養(yǎng)細(xì)胞樣本。

Hanks 博士手里現(xiàn)在有 N 種細(xì)胞，編號(hào)從 1~N，一個(gè)第 i 種細(xì)胞經(jīng)過 1 秒鐘可以分裂為

Si個(gè)同種細(xì)胞（Si為正整數(shù)）。現(xiàn)在他需要選取某種細(xì)胞的一個(gè)放進(jìn)培養(yǎng)皿，讓其自由分裂，

進(jìn)行培養(yǎng)。一段時(shí)間以后，再把培養(yǎng)皿中的所有細(xì)胞平均分入 M 個(gè)試管，形成 M 份樣本，

用于實(shí)驗(yàn)。Hanks 博士的試管數(shù) M 很大，普通的計(jì)算機(jī)的基本數(shù)據(jù)類型無法存儲(chǔ)這樣大的

M 值，但萬幸的是，M 總可以表示為 m1的 m2次方，即

M = m1^m2

，其中 m1，m2均為基本

數(shù)據(jù)類型可以存儲(chǔ)的正整數(shù)。

注意，整個(gè)實(shí)驗(yàn)過程中不允許分割單個(gè)細(xì)胞，比如某個(gè)時(shí)刻若培養(yǎng)皿中有 4 個(gè)細(xì)胞，

Hanks 博士可以把它們分入 2 個(gè)試管，每試管內(nèi) 2 個(gè)，然后開始實(shí)驗(yàn)。但如果培養(yǎng)皿中有 5

個(gè)細(xì)胞，博士就無法將它們均分入 2 個(gè)試管。此時(shí)，博士就只能等待一段時(shí)間，讓細(xì)胞們繼

續(xù)分裂，使得其個(gè)數(shù)可以均分，或是干脆改換另一種細(xì)胞培養(yǎng)。

為了能讓實(shí)驗(yàn)盡早開始，Hanks 博士在選定一種細(xì)胞開始培養(yǎng)后，總是在得到的細(xì)胞“剛

好可以平均分入 M 個(gè)試管”時(shí)停止細(xì)胞培養(yǎng)并開始實(shí)驗(yàn)。現(xiàn)在博士希望知道，選擇哪種細(xì)

胞培養(yǎng)，可以使得實(shí)驗(yàn)的開始時(shí)間最早。

輸入輸出格式

輸入格式：

第一行有一個(gè)正整數(shù) N，代表細(xì)胞種數(shù)。

第二行有兩個(gè)正整數(shù) m1，m2，以一個(gè)空格隔開，

即表示試管的總數(shù) M = m1^m2。

第三行有 N 個(gè)正整數(shù)，第 i 個(gè)數(shù) Si表示第 i 種細(xì)胞經(jīng)過 1 秒鐘可以分裂成同種細(xì)胞的個(gè)

數(shù)。

?

輸出格式：

輸出文件 cell.out 共一行，為一個(gè)整數(shù)，表示從開始培養(yǎng)細(xì)胞到實(shí)驗(yàn)?zāi)軌蜷_始所經(jīng)過的

最少時(shí)間（單位為秒）。

如果無論 Hanks 博士選擇哪種細(xì)胞都不能滿足要求，則輸出整數(shù)-1。

?

輸入輸出樣例

輸入樣例#1：
1 2 1 3 輸出樣例#1：
-1 輸入樣例#2：
2 24 1 30 12 輸出樣例#2：
2

說明

【輸入輸出說明】

經(jīng)過 1 秒鐘，細(xì)胞分裂成 3 個(gè)，經(jīng)過 2 秒鐘，細(xì)胞分裂成 9 個(gè)，……，可以看出無論怎么分

裂，細(xì)胞的個(gè)數(shù)都是奇數(shù)，因此永遠(yuǎn)不能分入 2 個(gè)試管。

【輸入輸出樣例2 說明】

第 1 種細(xì)胞最早在3 秒后才能均分入24 個(gè)試管，而第2 種最早在2 秒后就可以均分（每

試管144/(241)=6 個(gè)）。故實(shí)驗(yàn)最早可以在2 秒后開始。

【數(shù)據(jù)范圍】

對(duì)于 50%的數(shù)據(jù)，有m1^m2 ≤ 30000。

對(duì)于所有的數(shù)據(jù)，有1 ≤N≤ 10000，1 ≤m1 ≤ 30000，1 ≤m2 ≤ 10000，1 ≤ Si ≤ 2,000,000,000。

NOIP 2009 普及組 第三題

?

怎么說呢，一看到題目就想到了正解，然后開始拆分，理由不再贅述。

然而剛開始的時(shí)候TLE了，其實(shí)沒必要把每一個(gè)都拆開，只需要判斷就可以了

#include <cstdio> #include <cstring> #include <string> #include <iostream> #define INF 2000100 using namespace std; int a[10001]; struct node{int num;int sum; }; node p1[201]; node p2[201]; int ans=INF; int gcd (int a,int b) {return b==0?a:gcd(b,a%b); } int main() {int n,m1,m2;scanf("%d%d%d",&n,&m1,&m2);if (m1==1){cout<<"0"<<endl;return 0;}for (int i=1;i<=n;++i) scanf("%d",&a[i]);int t=1,t1=0;while (m1>1){t++;if (m1%t==0){t1++;p1[t1].num=t;p1[t1].sum=0;}int flag=0;while (m1%t==0){flag=1;m1/=t;p1[t1].sum++;}if (flag) p1[t1].sum*=m2;} /* for (int i=1;i<=n;++i){int t=1,t2=0;while (a[i]>1){t++;if (a[i]%t==0){t2++;p2[t2].num=t;p2[t2].sum=0;}int flag=0;while (a[i]%t==0){flag=1;a[i]/=t;p2[t2].sum++;}}int x=1,y=1;int now=-1;do{while (x<=t1){while (p2[y].num!=p1[x].num&&y<=t2) y++;if (y>t2) {now=INF;break;}now=max(now,p1[x].sum%p2[y].sum==0?p1[x].sum/p2[y].sum:p1[x].sum/p2[y].sum+1);x++;}break;}while(1);ans=min(ans,now);}*/for (int i=1;i<=n;++i){int flag=1;int now=-1; for (int j=1;j<=t1;++j){if (a[i]%p1[j].num!=0){flag=0; break;}else {int t=0;while(a[i]%p1[j].num==0){a[i]/=p1[j].num;t++;}now=max(now,p1[j].sum%t==0?p1[j].sum/t:p1[j].sum/t+1);}}if (flag) ans=min(ans,now);}if (ans==INF) cout<<"-1"<<endl;else cout<<ans<<endl; }

?

?

注釋部分就是自己思想的掙扎

轉(zhuǎn)載于:https://www.cnblogs.com/AwesomeOrion/p/5428599.html

總結(jié)

以上是生活随笔為你收集整理的#include NOIP2009 Junior 细胞分裂 ——using namespace wxl;的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。