細胞分解（數論題）
- 一 題目描述
- 二 解題思路
- 一 手寫分析
- 二 簡要概括
- 三 題解代碼
- 四 每日共勉
一 題目描述
題目鏈接: link.
二 解題思路
整體分析：用到了歐拉篩＋整數分解，
一 手寫分析
二 簡要概括
①歐拉篩，篩出3000以內的素數，放在sum_prime陣列中，
②大整數分解
③判斷是否可以覆寫
④依次比較每個細胞所用時間t，選取最小值，
三 題解代碼
// A code block
var foo = 'bar';
#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int n,i,j,m1,m2,minn=2147483647;
int prime[maxn]={0}; //30000以內所有的質數
bool flag=false,here; //flag為所有細胞，here為單個細胞的判斷
int pipe_prime[maxn]; //試管的質因數分解
int cell_prime[maxn]; //細胞的質因數分解
int sum_prime=0,cell,now; //30000以內質數總數記為sum_prime
bool pr(int k) //判斷是否為素數，不予以注釋
{
int m;
for(m=2;m<=floor(sqrt(k));m++)
if(k%m==0)return false;
return true;
}
int main() //主程式開始
{
cin>>n; cin>>m1>>m2;
for(i=2;i<=maxn;i++) //把30000以內的質因數列舉出來
if(pr(i))
{
sum_prime++;
prime[sum_prime]=i;
}
i=1; while(m1!=1) //為m1質因數分解
{
if(m1%prime[i]==0)
while(m1%prime[i]==0) //除到沒有為止
{pipe_prime[i]+=m2; m1/=prime[i]; }
i++;
}
for(i=1;i<=n;i++)
{
cin>>cell; j=1; now=0; here=true; //初始化
memset(cell_prime,0,sizeof(cell_prime)); //初始化，加頭檔案cstring
while(j<=sum_prime) //大于30000的質因子忽略，即在30000內質因數分解
{
if(cell%prime[j]==0)
while(cell%prime[j]==0)
{cell_prime[j]++; cell/=prime[j]; }
j++;
}
for(j=1;j<=sum_prime;j++)
{
if(pipe_prime[j]!=0&&cell_prime[j]==0)here=false; //如果細胞沒有試管所擁有的質因子，該細胞不可用
if(pipe_prime[j]!=0&&cell_prime[j]!=0) //如果試管沒有該質因子，不用做
{
if(pipe_prime[j]%cell_prime[j]==0)
now=max(now,pipe_prime[j]/cell_prime[j]);
else now=max(now,pipe_prime[j]/cell_prime[j]+1); //記得要+1，整除時不用加
}
}
if(here){flag=true; if(now<minn)minn=now;} //如果該細胞可行，做個標志，替換
}
if(flag)cout<<minn<<endl; //如果可行
else cout<<-1<<endl;
return 0;
}
四 每日共勉
天行健，君子以自強不息，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/273768.html
標籤：其他
上一篇：HCLA綜合實驗