6.[NOIP2009 普及组] 细胞分裂 难度：普及- 来源：NOIP普及组 AC代码（C++）： 此处英文注释为自己靠着自己的英语知识使用百度翻译（fanyi.baidu.com/#zh/en/）所写，请酌情添加

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) { f[i] = 150000; break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) { f[i] = 150000; break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; if (an > f[i]) f[i] = an； } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

思路 一道数学题。(可以好好欣赏美丽的LATEX\bold L\bold A\bold T\bold E\bold XLATEX公式了) 先来看看题目要做什么：枚举SinS^n_iSin (nnn为这里的秒数)，使得保证m1m2∣Sinm^{m2}_1|S^n_im1m2 ∣Sin (即SinS^n_iSin 被m1m2m^{m2}_1m1m2 整除)时，nnn最小。 显然对于1≤m1≤30000,1≤m2≤100001\leq m_1\leq 30000,1\leq m_2 \leq 100001≤m1 ≤30000,1≤m2 ≤10000这样的数据，我们是存不下MMM的数值的，更不用说对MMM进行一系列的操作和计算了。但是题目中给出的M=m1m2M=m^{m2}_1M=m1m2 的条件很有意思，结合着我们需要满足m1m2∣Sinm^{m2}_1|S^n_im1m2 ∣Sin 的目的，不难看出这个条件是暗示让我们对MMM和SIS_ISI 进行质因数分解，然后再通过质因数和其指数判断是否能满足m1m2∣Sinm^{m2}_1|S^n_im1m2 ∣Sin 。 而这样，我们就成功地将一个乘方的计算，转换成了指数相乘的计算。(((若m1=p1ip2j...pnk,m_1=p^i_1p^j_2...p^k_n,m1 =p1i p2j ...pnk ,则m1m2=p1m2 ip2m2 j...pnm2 km^{m2}_1=p^{m_2\ i}_1p^{m_2\ j}_2...p^{m_2\ k}_nm1m2 =p1m2  i p2m2  j ...pnm2  k ))) 那么怎么判断是否满足m1m2∣Sinm^{m2}_1|S^n_im1m2 ∣Sin 呢，举个栗子： p1p_1p1 p2p_2p2 p3p_3p3 p4p_4p4 p5p_5p5 p6p_6p6 MMM 2 3 3 3 4 0 S1nS^n_1S1n 1 x nnn 2 x nnn 1 x nnn 1 x nnn 1 x nnn 0 x nnn 只要满足对于MMM的每一个质因数ppp，它的指数都要比SinS^n_iSin 来的小即可。在这里，1 x n≥5n\geq 5n≥5, 取最小的nnn为555。我们可以循环每一个MMM的质因数，然后让nnn取能够满足规定指数大小关系的最小值，最后对于每一个SiS_iSi 打擂台求出最后nnn的最小值。 什么时候永远也不能满足要求呢？那就是当MMM中有SIS_ISI 没有的质因数的时候。因为无论给SIS_ISI 乘多少次方，都不可能创造新的质因数。就比如若MMM的质因子p6p_6p6 指数为1时，就不可能满足要求。 最后，怎么把质因数和它的指数存下来呢，我们注意到题目规定1≤m1≤300001\leq m_1\leq 300001≤m1 ≤30000如果开30000大小的数组就造成了浪费，小于30000的质数只有3300左右个，我们可以在初始化时先跑一遍质数存下来，以便后期使用。 对了，还有一个特判，也就是当 m1=1m_1=1m1 =1时，怎样都可以均分，应该直接输出0否则进入后面由于1不是质数，会输出 -1。 AC代码

不回复几点睡的三姑夫i护肤hiuof恒大华府idif欧迪芬（激动） 想了一天一夜才做出来的 下面是代码

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { }

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) { f[i] = 150000; break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

> 这题因该是普及+才对呀 【做题背景】数学题，秒杀！ 【算法名称】质因数分解 【算法分析】题目即要求最小的正整数 k 使得有一个 i（1 n）i（1~n）i（1 n），满足 sik∣m1m2si^k|m1^m2sik∣m1m2。 以样例二为例，241=24=23∗324^1=24=2^3*3241=24=23∗3 对于细胞一，30=2∗3∗530=2*3*530=2∗3∗5 要使每一个质因数均满足要求， 最小值now的计算过程为： step 1：对于质因子2，now=3now=3now=3 step 2：对于质因子3，now=3now=3now=3 对于细胞二，12=22∗312=2^2*312=22∗3 要使每一个质因数均满足要求， 最小值now的计算过程为： step 1：对于质因子2，now=2now=2now=2 step 2：对于质因子3，now=2now=2now=2 所以，min值为2 算法结束~~~ 【注意事项】 1.对于30，质因子5没有任何用处，因为 30k30^k30k 应为24的倍数。 2.把30000以内所有质数都枚举出来应该会更快。 3.质因数分解的过程千万不能写错（别忘了把 m1m1m1 的质因子个数都 ∗m2*m2∗m2 哦）！ 4.请勿抄袭题解！ 贴上华丽的代码：

#include <iostream> #include <cstdio> #include <memory.h> #define int long long using namespace std; int a[100005], b[100005]; signed main(){ int n, m, k, tmp; cin >> n >> m >> k; for(int i = 2; i * i <= m; i++){ while(m % i == 0) a[i] += k, m /= i; }a[m] += k; int mn = 0x3f3f3f3f; for(int i = 1; i <= n; i++){ memset(b, 0, sizeof(b)); int mx = 0; cin >> tmp; for(int j = 2; j * j <= tmp; j++){ while(tmp % j == 0) b[j], tmp /= j; }if(tmp > 100000) continue; b[tmp]; for(int j = 2; j <= 100000; j++){ if(!a[j]) continue; if(!b[j]) goto test; mx = max(mx, a[j] / b[j] + bool(a[j] % b[j])); } if(1 + 1 == 3){ test: continue; } mn = min(mn, mx); } cout << (mn == 0x3f3f3f3f ? -1 : mn); }

#include<bits/stdc++.h> using namespace std; int prime[3310],mx[3310],sx[3310],s[10010]; bool isprime(int n) { for(int i=2;ii<=n;i++) if(n%i0)return false; return true; } int main() { int n,m1,m2,tot=0,minn=1<<30,flag=0,np,ff=0; prime[++tot]=2; for(int i=3;i<=30000;i+=2) if(isprime(i)) prime[tot]=i; scanf("%d %d %d",&n,&m1,&m2); for(int i=1;i<=n;i)scanf("%d",&s[i]); if(m11) { printf("0"); return 0; } for(int i=1;prime[i]<=m1;i++) { while(m1%prime[i]==0) { m1/=prime[i]; mx[i]++; } mx[i]=m2; } for(int i=1;i<=n;i++) { memset(sx,0,sizeof(sx)); for(int j=1;j<=tot;j++) { while(s[i]%prime[j]==0) { s[i]/=prime[j]; sx[j]; } } np=1;//每一次的n flag=0; for(int j=1;j<=tot;j) { if(mx[j]&&sx[j]) { flag=1; if(mx[j]>sx[j]*np)np=mx[j]/sx[j]; if(mx[j]>sx[j]*np)np++; } else if(mx[j]&&!sx[j]){flag=false;break;} } if(flag)minn=min(minn,np),ff=1; } if(ff)printf("%d",minn); else printf("-1"); return 0; }

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } // If the number of tubes is 1, the conditions are met directly 若试管数为1，直接符合条件 for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { // Quality finding factor 找质因数 if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) // Number of quality finding factors 找质因数个数 { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) // If it is a prime number, the prime factor is itself 若为质数，质因数为本身 { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) // If there is no certain factor, break directly { f[i] = 150000; // Maximum: 10000 * log 2 30000 break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; // Equivalent to ceil function if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

有点奇怪？ #include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { if (p[i]) { if (m1 % i == 0) { prime[size][1] = i; prime[size][2] = 1; } } int tim = 2; while (tim * i <= m1) { p[tim * i] = 0; tim; } } for (i = 1; i <= size; i++) { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) { f[i] = 150000; break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }

本人第一篇题解

#include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 7; struct Nums{ int prime; int cnt; }p[maxn]; int a[maxn]; int m1, m2; int n; int total = 0; void div(int num){ if (num == 1){ return ; } for (int i = 2; i * i <= num; i){ if (num % i == 0){ p[total].prime = i; while (num % i == 0){ num /= i; p[total].cnt; } p[total].cnt *= m2; } } if(num != 1){ p[total].prime = num; p[total].cnt = m2; } return ; } bool check(int x){ for (int i = 1; i <= total; i){ if (x % p[i].prime != 0){ return 0; } } return true; } int minn = INT_MAX; void cultivate(int x){ int maxx = 0; for (int i = 1; i <= total; i){ int tmp = 0; while (x % p[i].prime == 0){ tmp++; x /= p[i].prime; } int ans = (p[i].cnt - 1) / tmp + 1; maxx = max(maxx, ans); } minn = min(minn, maxx); return ; } signed main(){ cin >> n; cin >> m1 >> m2; div(m1); for (int i = 1; i <= n; i++){ cin >> a[i]; if (check(a[i]) == 0){ continue; } cultivate(a[i]); } if (minn == INT_MAX){ cout << -1; } else{ cout << minn ; } return 0; }

#include <bits/stdc++.h> using namespace std; int n,m1,m2,ans = 150000; int i,j; int s[10001],f[10001]; bool p[30001]; int prime[501][3],size = 0; int main(void) { memset(p,1,sizeof(p)); memset(f,0,sizeof(f)); scanf("%d%d%d",&n,&m1,&m2); if (m1 == 1) { printf("0"); return 0; } for (i = 1; i <= n; i++) scanf("%d",&s[i]); int xx = floor(sqrt(m1)); for (i = 2; i <= xx; i++) { } for (i = 1; i <= size; i++) { int num = prime[i][1]; while (m1 % (num * prime[i][1]) == 0) { num *= prime[i][1]; prime[i][2]; } prime[i][2] *= m2; } if (size == 0) { prime[size][1] = m1; prime[size][2] = m2; } for (i = 1; i <= n; i) { for (j = 1; j <= size; j) { if (s[i] % prime[j][1] != 0) { f[i] = 150000; break; } int tim = 1; long long num = prime[j][1]; while (s[i] % (num * prime[j][1]) == 0) { num *= prime[j][1]; tim++; } int an = (prime[j][2]-1) / tim + 1; if (an > f[i]) f[i] = an; } } for (i = 1; i <= n; i++) if (ans > f[i]) ans=f[i]; if (ans == 150000) printf("-1"); else printf("%d",ans); return 0; }