[NOIP 2009 普及组] 细胞分裂

知识点

质因数分解、整除条件、指数比较

解题思路

分解m1，某质因数在m1指数为e，则试管数要求指数e·m2。对每种细胞si，统计这些质因数各有多少次幂v；若缺某个质因数便不可行，否则所需时间为各ceil(e·m2/v)的最大值，最后取所有细胞的最小值。m1=1时初始一个细胞就可分入一个试管，答案0。

正确性说明

si^t能被m1^m2整除当且仅当每个目标质因数的指数至少达到要求。每项独立给出t的下界，最大下界恰是该细胞最早时间。任一种细胞都可选，取最小即全局最早。

易错点

si额外的质因数不影响；si=1不能提供目标因子；m1=1要单独处理；不能实际构造巨大幂。

复杂度

分解O(√m1)，对N种细胞逐目标因子除尽，时间O(N·log si·ω(m1))，空间O(ω(m1))。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,m1,m2;cin>>n>>m1>>m2;vector<pair<int,int>>fac;int x=m1;for(int p=2;p*p<=x;p++)if(x%p==0){int e=0;while(x%p==0)x/=p,e++;fac.push_back({p,e*m2});}if(x>1)fac.push_back({x,m2});int ans=INT_MAX;for(int i=0;i<n;i++){int v;cin>>v;int t=0;bool ok=true;for(auto [p,need]:fac){int k=0;while(v%p==0)v/=p,k++;if(!k){ok=false;break;}t=max(t,(need+k-1)/k);}if(ok)ans=min(ans,t);}cout<<(ans==INT_MAX?-1:ans)<<'\n';}