首页 > 代码库 > [NOIP2009普及组]细胞分裂
[NOIP2009普及组]细胞分裂
题目：洛谷P1069、Vijos P1814、codevs1152。
题目大意：给你一个$m_1$和$m_2$，和n个数$s_i$，要你求这n个数中是否有一个数满足$s_i ^t \equiv 0(mod\ m_1^{m_2})$，如果有则输出最小的t，没有输出-1。
解题思路：由于$m_1^{m_2}$最大能达到$30000^{10000}$，直接判断显然是不可能的。
我们可以把$m_1$和$s_i$分解质因数，那么就有$s_i ^t =p_1^{a_1}p_2^{a_2}...p_k^{a_k},m_1=q_1^{b_1}q_2^{b_2}...q_k^{b_k}$。
进而可以得出：$s_i^t=p_1^{ta_1}p_2^{ta_2}...p_k^{ta_k},m_1^{m_2}=q_1^{m_2b_1}q_2^{m_2b_2}...q_k^{m_2b_k}$。
如果$s_i$的若干次方要是$m_1^{m_2}$的倍数，那么它本身必须含有$m_1$的所有质因子，如果满足这个条件，那么对于相同的质因子，$\lceil \frac{b_km_2}{a_k}\rceil$就是所需的次数。这些次数的最大值就是t的答案。最终答案就是所有t的最小值。
此题只要分解质因数的效率不低，就不会超时，我之前就是因为分解质因数效率太低而TLE。
C++ Code：
#include<cstdio>#include<cstring>#include<cctype>using namespace std;struct prime{ int cnt,pn[30001],s[30001];}p,q;inline int readint(){ char c=getchar(); while(!isdigit(c))c=getchar(); int p=0; while(isdigit(c))p=(p<<3)+(p<<1)+(c^‘0‘),c=getchar(); return p;}int n,m1,m2;void fenjie(int t,prime& p){ p.cnt=0; for(int i=2;i*i<=t;++i) if(!(t%i)){ p.pn[++p.cnt]=i; p.s[p.cnt]=0; do{ t/=i; ++p.s[p.cnt]; }while(!(t%i)); } if(t>1){ p.pn[++p.cnt]=t; p.s[p.cnt]=1; }}int main(){ n=readint(),m1=readint(),m2=readint(); if(m1==1){ puts("0"); return 0; } fenjie(m1,p); int ans=-1,x; while(n--){ x=readint(); fenjie(x,q); int mx=0,nxt=1; bool ok=false; if(q.cnt>=p.cnt) for(int i=1;i<=p.cnt;++i){ while(q.pn[nxt]<p.pn[i]&&nxt<=q.cnt)++nxt; if(nxt>q.cnt||q.pn[nxt]>p.pn[i])break; int f=p.s[i]*m2/q.s[nxt]; if(p.s[i]*m2%q.s[nxt])++f; if(mx<f)mx=f; ok=i==p.cnt; } if(ok&&(ans==-1||ans>mx))ans=mx; } printf("%d\n",ans); return 0;}
[NOIP2009普及组]细胞分裂
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。