2009NOIP普及组真题 3. 细胞分裂

本文主要是介绍2009NOIP普及组真题 3. 细胞分裂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

线上OJ：

一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1947

核心思想：

本题的意思是 在所有的 $Si$ 中，找一个 $S{i}^t$ 最早能被 $m{1}^{m2}$ 整除。
上述若能整除，则说明:
1、$m1$ 的质因数肯定是 $Si$ 质因数的子集 （换句话说，m1 的质因数都是 Si 的因数。如果 $m1$ 中某个质因数不能整数 $Si$，则整个 $S{i}^t$ 不可能被 $m{1}^{m2}$ 整除）
2、若 $m1$ 的质因数本身是多次幂（比如 $m1$ 为40，则 $m1=2\ast 2\ast 2\ast 5=2^3\ast 5$，即质因数2的幂次为3，质因数5的幂次为1）。若此时的 m2 是2，则
$m{1}^{m2}=(2^3\ast 5^1{)}^2=(2^{3\ast 2})\ast (5^{1\ast 2})=2^6\ast 5^2$。

如果此时 $Si$ 的质因数中，2有6个，5有2个，则 1 秒后到达 $Si$ 即可直接整除 $m{1}^{m2}$
如果此时 Si 的质因数中，2有3个，5有1个，则2个周期后可整除 $m{1}^{m2}$
如果此时 Si 的质因数中，2有2个，5有1个，则3个周期后才能整除 $m{1}^{m2}$

故，$Si$ 的分裂周期为 $Si$ 的质因数中分裂周期最多的那个

关键步骤：

1、先计算 $m1$ 的质因数，存储到数组 $p[i]$ 中；用 $c[i]$ 记录质因数 $p[i]$ 的个数。
2、如果是质数，要单独考虑
3、如果m1为1，则无需计算，直接输出
4、在读入每个 $Si$ 时按以下步骤进行：
a. 检查m1的每一个质因数是否都是 Si 的因数，如果有一个不是，则Si不可能被除尽
b. 检查每一个质因数在 Si 中出现的次数
c. 求出每一个质因数需经过几个周期方能被 $m1$ 中对应的幂次整除

举例：$Si$ 为800，m1为40，m2 是2。则 $Si=2^5\ast 5^2，m{1}^{m2}=2^6\ast 5^2$。细胞 Si 经过一个周期变为 $2^5\ast 5^2$，无法被 $2^6\ast 5^2$ 整除，经过两个周期变为 $2^{10}\ast 5^4$，可以被 $2^6\ast 5^2$ 整除。所以 Si=800的需要2个周期。

d. 找出 Si 的所有质因数中分裂周期最多的那个
5、所有的 Si 都读完后，找出分裂周期最小的数值，就是本题的答案。

题解代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;const int N = 30005;int n, m1, m2, s, ans, maxn;
// p[i]记录m1的第i个质因数，c[i]表示m1的第i个质因数的个数。比如12=2*2*3,所以p[1]=2,c[1]=2,p[2]=3,c[2]=1
int p[N], c[N], cnt = 0; // cnt记录m1的质因数的个数。比如 12的质因数是2和3，则cnt=2
bool isprime = true; // m1是否为质数int main()
{scanf("%d %d %d", &n, &m1, &m2);if(m1 == 1)  // 如果m1为1，说明就1个试管，直接放即可{printf("0\n");return 0;}int x = m1;for(int i = 2; (i*i <= m1) && x; i++) // 求出m1的所有质因数，以及每个质因数的个数{if( x % i == 0 ) // 如果存在i能整除m1{isprime = false;  // 如果找到一个质因数，则m1不是质数p[++cnt] = i; // 将质因数 i 存到p数组里，p数组从p[1]开始}while( x % i == 0 ){c[cnt]++; // 记录m1的质因数 i 的个数x /= i;}        }if(isprime) // 如果是质数，则上述for循环无法找到质因数。{p[++cnt] = m1; // 质数的质因数只有自己c[cnt] = 1;}ans = INF;while(n--) // 读入n个数，逐次判断{maxn = -INF; // 每一轮开始前，先初始化。maxn 记载读入s需要分裂的周期bool flag = true;scanf("%d", &s);for(int i = 1; i <= cnt && s; i++)  // 检查m1的每一个质因数是否都是s的因数{int a = 0;if(s % p[i]) // 如果m1的质因数p[i]不是s的因数，则s不可能被m1^m2除尽{flag = false;break;}while(s % p[i] == 0)  // 如果能除尽，则统计s内有多少个p[i]{a++;s /= p[i];}maxn = max(maxn, (c[i]*m2 + a - 1)/a); // s的分裂周期为s的质因数中分裂周期最多的那个。举例：质因数2需要分裂5次能满足，质因数3需要分裂2次就能满足，则s的分裂周期为5}if(!flag) continue;ans = min(ans, maxn);  // 在所有的s种，找一个分裂周期最小的}if(ans == INF) printf("-1\n");else  printf("%d\n", ans);return 0;
}

这篇关于2009NOIP普及组真题 3. 细胞分裂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---