馬上又要有一年的NOIP----NOIP2018

　　作為一個去年考掛的退役選手，在這最后的時間復習復習。臨陣磨槍吧.....

　　學的東西都忘了好多.....畢竟一年都沒有在看過信競了

　　不廢話看題↓

　　

描述 Description
Hanks 博士是 BT (Bio-Tech，生物技術) 領域的知名專家。現(xiàn)在，他正在為一個細胞實 驗做準備工作：培養(yǎng)細胞樣本。

Hanks 博士手里現(xiàn)在有 N 種細胞，編號從 1~N，一個第 i 種細胞經(jīng)過 1 秒鐘可以分裂為Si 個同種細胞（Si 為正整數(shù)）。
現(xiàn)在他需要選取某種細胞的一個放進培養(yǎng)皿，讓其自由分裂，進行培養(yǎng)。一段時間以后，再把培養(yǎng)皿中的所有細胞平均分入 M 個試管，形成 M 份樣本，用于實驗。
Hanks 博士的試管數(shù) M 很大，普通的計算機的基本數(shù)據(jù)類型無法存儲這樣大的M 值，
但萬幸的是，M 總可以表示為 m1 的 m2 次方，即 M = m1^m2 ，其中 m1，m2均為基本數(shù)據(jù)類型可以存儲的正整數(shù)。

注意，整個實驗過程中不允許分割單個細胞，比如某個時刻若培養(yǎng)皿中有4個細胞，
Hanks 博士可以把它們分入 2 個試管，每試管內(nèi) 2 個，然后開始實驗。
但如果培養(yǎng)皿中有 5 個細胞，博士就無法將它們均分入 2 個試管。
此時，博士就只能等待一段時間，讓細胞們繼 續(xù)分裂，使得其個數(shù)可以均分，或是干脆改換另一種細胞培養(yǎng)。

為了能讓實驗盡早開始，Hanks 博士在選定一種細胞開始培養(yǎng)后，總是在得到的細胞“剛 好可以平均分入 M個試管”時停止細胞培養(yǎng)并開始實驗。現(xiàn)在博士希望知道，選擇哪種細 胞培養(yǎng)，可以使得實驗的開始時間最早。

輸入格式 Input Format
第一行有一個正整數(shù) N，代表細胞種數(shù)。

第二行有兩個正整數(shù) m1，m2，以一個空格隔開， m1^m2 即表示試管的總數(shù) M。

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

輸出格式 Output Format
共一行，為一個整數(shù)，表示從開始培養(yǎng)細胞到實驗能夠開始所經(jīng)過的 最少時間（單位為秒）。
如果無論 Hanks 博士選擇哪種細胞都不能滿足要求，則輸出整數(shù)-1。

樣例輸入 Sample Input

輸入樣例1：
1
2 1
3

?

輸入樣例2：
2
24 1
30 12

樣例輸出 Sample Output

輸出樣例1：
-1

?

輸入樣例2：
2

時間限制 Time Limitation
1s
注釋 Hint
【輸入輸出樣例 1 說明】
經(jīng)過 1 秒鐘，細胞分裂成 3 個，經(jīng)過 2 秒鐘，細胞分裂成 9 個，……，可以看出無論怎么分 裂，細胞的個數(shù)都是奇數(shù)，因此永遠不能分入 2 個試管。

【輸入輸出樣例 2 說明】
第 1 種細胞最早在 3 秒后才能均分入 24 個試管，而第 2 種最早在 2 秒后就可以均分（每 試管 144/(241)=6 個）。故實驗最早可以在 2 秒后開始。

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

對于 50%的數(shù)據(jù)，有 m1^m2≤ 30000。
對于所有的數(shù)據(jù)，有 1 ≤ N ≤ 10000，1 ≤ m1 ≤ 30000，1 ≤ m2 ≤ 10000，1 ≤ Si ≤ 2,000,000,000。
來源 Source
noip2009 普及

?

　　前一段大概看了看圖論，今天復習了一下數(shù)論//基礎，看到這個題，又重新想了想。

　　思路：

　　數(shù)據(jù)最大是30000^10000顯然是不可能讓你直接算的，所以我們想到質(zhì)因數(shù)分解。

　　因為要讓細胞分裂t個時間變得可以分到m1^m2個試管中，這我們就可以發(fā)現(xiàn)，我們需要讓細胞數(shù)是這試管個數(shù)的倍數(shù)

　　所以我們怎么辦呢？

　　我們可以吧m1質(zhì)因數(shù)分解，求出其每個質(zhì)因數(shù)的個數(shù)。這每個質(zhì)因數(shù)的個數(shù)在乘以m2就是m1^m2的質(zhì)因數(shù)的個數(shù)。

　　然后我們在把每單位時間細胞分裂數(shù)Si進行質(zhì)因數(shù)分解。

　　然后既然要在t時間后細胞可以被均分，所以我們就要在t時間后細胞數(shù)的每個質(zhì)因數(shù)的個數(shù)都大于m1^m2的每個質(zhì)因數(shù)的個數(shù)//理解下

　　這樣這道題就變得簡單了，代碼如下

　　

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define MAXN 51000 7 using namespace std; 8 int f[MAXN],a[MAXN],b[MAXN]; 9 int m1,m2,len,l; 10 int prime[MAXN]; 11 void shai(int x) 12 { 13 memset(f,1,sizeof(f)); 14 for(int i=2;i<=x;i++) 15 { 16 if(f[i]) 17 for(int j=i+i;j<=x;j+=i) 18 f[j]=0; 19 } 20 for(int i=2;i<=x;i++) 21 if(f[i]) 22 prime[++len]=i; 23 } 24 void QAQ(int x) 25 { 26 memset(b,0,sizeof(b)); 27 for(int i=1;i<=len&&prime[i]<=x;i++) 28 { 29 l=i; 30 while(x%prime[i]==0) 31 { 32 b[prime[i]]++; 33 x/=prime[i]; 34 } 35 b[prime[i]]*=m2; 36 } 37 } 38 void QWQ(int x) 39 { 40 memset(a,0,sizeof(a)); 41 for(int i=1;i<=len&&prime[i]<=x;i++) 42 { 43 while(x%prime[i]==0) 44 { 45 a[prime[i]]++; 46 x/=prime[i]; 47 } 48 } 49 } 50 int find() 51 { 52 int maxx=0,h; 53 for(int i=1;i<=l;i++) 54 { 55 if(b[prime[i]]!=0) 56 { 57 if(a[prime[i]]==0) 58 return -1; 59 h=b[prime[i]]/a[prime[i]]; 60 if(b[prime[i]]%a[prime[i]]==0) 61 maxx=max(h,maxx); 62 else 63 maxx=max(h+1,maxx); 64 } 65 } 66 return maxx; 67 } 68 int main() 69 { 70 len=0; 71 shai(51000); 72 int n; 73 cin>>n; 74 cin>>m1>>m2; 75 QAQ(m1); 76 int ans=9999999; 77 for(int i=1;i<=n;i++) 78 { 79 int x; 80 cin>>x; 81 QWQ(x); 82 int h=find(); 83 if(h!=-1) 84 ans=min(h,ans); 85 } 86 if(ans==9999999) 87 cout<<-1<<endl; 88 else 89 cout<<ans<<endl; 90 return 0; 91 } Think！

?

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

總結(jié)

以上是生活随笔為你收集整理的【复习】---【noip2009 普及】细胞问题 (1)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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