noip2009 细胞分裂 (质因数分解,处理大数间能否整除)
P1814细胞分裂
Accepted
描述Hanks 博士是BT (Bio-Tech,生物技术) 领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。 格式输入格式共有三行。 输出格式共一行,为一个整数,表示从开始培养细胞到实验能够开始所经过的最少时间(单位为秒)。? 样例1样例输入1[复制]
1 2 1 3 样例输出1[复制]
-1 样例2样例输入2[复制]
2 24 1 30 12 样例输出2[复制]
2 限制每个测试点1s。 提示样例1说明: 来源NOIP2009普及组 代码:
#include<cstdio> #include<algorithm> #define maxn 10000 #define inf 1000000000 using namespace std; int n,m1,m2; int p[maxn],q[maxn]; int main() { int i,j,k,s,x,ans; scanf("%d%d%d",&n,&m1,&m2); if(m1==1){printf("0n");return 0;} for(i=2;m1>=i && m1>0;i++) if(m1%i==0) { p[++p[0]]=i; while(m1%i==0)++q[p[0]],m1/=i; q[p[0]]*=m2; } for(ans=inf,i=1;i<=n;i++) { scanf("%d",&s); for(x=0,j=1;j<=p[0];j++) { if(s%p[j]!=0){x=inf;break;} k=0;while(s%p[j]==0)++k,s/=p[j]; if(q[j]%k==0)x=max(x,q[j]/k); else x=max(x,q[j]/k+1); } ans=min(ans,x); } if(ans==inf)printf("-1n"); else printf("%dn",ans); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |