细胞分裂(数论) 傷城~ 2021-11-09 00:08 303阅读 0赞 [题目链接][Link 1] 题意: 给你m1^m2个容器,现在有n种细胞,每种细胞每次会分裂成si个,问能够能够平均分配給m1^m2个容器的最少分裂次数; 思路: 分别考虑每一种细胞,求出他们最少分裂的次数,最后去最小值即可; 假设第i种细胞至少分裂k次可平均分配給容器,那么应该满足si^k=(m1^m2)\*p, p是一个整数。 如果a可以整除b,a和b,都用质数的乘积来表示。那么a的质数都可以在b中找到。 对于此题,我们先把m1分解(m2不影响质数,只影响质数的次数),之后我们分解每一个si,如果m1的每个质数都能在si中找到,说明可以被整除,反之只要有一个找不到,那么就说明该细胞无论分裂多少次都不可能满足条件。 对于能够整除的si,我们逐一判断每一个质数至少需要多少次分裂才能满足条件,最后取最大的一个即是该细胞最少的分裂次数; 1 #include<bits/stdc++.h> 2 using namespace std; 3 4 #define ll long long 5 const int N = 1e5+10; 6 int cnt[N],p[N],q[N],cnk[N]; 7 8 int main(){ 9 ios::sync_with_stdio(false); 10 cin.tie(0); cout.tie(0); 11 12 int m1,m2; 13 int ans=1e7; 14 int n;cin>>n; 15 cin>>m1>>m2; 16 if(m1==1){ 17 cout<<0<<endl; 18 return 0; 19 } 20 21 memset(cnt,0,sizeof(cnt)); 22 memset(p,0,sizeof(p)); 23 int res=1; 24 for(int i=2;i*i<=m1;i++){ 25 if(m1%i==0){ 26 cnt[res++]=i; 27 while(m1%i==0){ 28 p[i]++; 29 m1/=i; 30 } 31 } 32 } 33 34 if(m1>1)cnt[res++]=m1,p[m1]++; 35 36 for(int i=1;i<=n;i++){ 37 int s; 38 cin>>s; 39 40 bool f=false; 41 int flag=0; 42 43 memset(q,0,sizeof(q)); 44 45 for(int j=2;j*j<=s;j++){ 46 if(j>cnt[res-1])break; 47 if(s%j==0){ 48 while(s%j==0){ 49 q[j]++; 50 s/=j; 51 } 52 } 53 } 54 if(s>1&&s<=cnt[res-1])q[s]++; 55 56 57 for(int j=1;j<res;j++){ 58 if(q[cnt[j]]==0){ 59 f=true; 60 break; 61 } 62 flag=max(flag,int(ceil(p[cnt[j]]*m2*1.0/q[cnt[j]]))); 63 } 64 65 if(!f)ans=min(ans,flag); 66 } 67 68 if(ans!=1e7)cout<<ans<<endl; 69 else cout<<-1 <<endl; 70 71 return 0; 72 73 } 转载于:https://www.cnblogs.com/chihong/p/11177951.html [Link 1]: https://ac.nowcoder.com/acm/contest/948/A?&headNav=acm&headNav=acm
还没有评论,来说两句吧...