细胞分裂（数论）

傷城~ 2021-11-09 00:08 298阅读 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