#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; }

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

题目大意是找到一个sk使得sk≡0( mod m1m2)即sk%m1m2==0且k最小题目大意是找到一个s^k使得s^k\equiv0(\bmod m1^{m2})即s^k\%m1^{m2}==0且k最小题目大意是找到一个sk使得sk≡0(modm1m2)即sk%m1m2==0且k最小 给你n个s让你求所有s对应k的最小值给你n个s让你求所有s对应k的最小值给你n个s让你求所有s对应k的最小值 一.M的处理一.M的处理一.M的处理 因为我们m2和m1过大所以无法直接处理出m1m2的值因为我们m2和m1过大所以无法直接处理出m1^{m2}的值因为我们m2和m1过大所以无法直接处理出m1m2的值 考虑素因(质)数分解考虑素因(质)数分解考虑素因(质)数分解 令M=m1=p1a1∗p2a2∗p3a3⋯(p1,p2,⋯均为素(质)数,a1,a2,⋯均为整数)即该式为m1的素(质)因数分解令M=m1=p_1^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}\cdots(p_1,p_2,\cdots均为素(质)数,a_1,a_2,\cdots均为整数)即该式为m1的素(质)因数分解令M=m1=p1a1 ∗p2 a2 ∗p3 a3 ⋯(p1 ,p2 ,⋯均为素(质)数,a1 ,a2 ,⋯均为整数)即该式为m1的素(质)因数分解 则M=m1m2=(p1a1∗p2a2∗p3a3⋯ )m2=p1a1m2∗p2a2m2∗p3a3m2⋯则M=m1^{m2}=(p_1^{a_1}*{p_2}^{a_2}*{p_3}^{a_3}\cdots)^{m2}=p_1^{a_1m2}*{p_2}^{a_2m2}*{p_3}^{a_3m2}\cdots则M=m1m2=(p1a1 ∗p2 a2 ∗p3 a3 ⋯)m2=p1a1 m2 ∗p2 a2 m2∗p3 a3 m2⋯ 那么我们可以维护每个pi和ai可以开个struct维护那么我们可以维护每个p_i和a_i可以开个struct维护那么我们可以维护每个pi 和ai 可以开个struct维护 二.S的处理二.S的处理二.S的处理 那面对2∗109的s我们肯定不能用素(质)因数分解那面对2*10^9的s我们肯定不能用素(质)因数分解那面对2∗109的s我们肯定不能用素(质)因数分解 因为我们要让sk%m1m2==0就是说sk是m1m2的倍数所以sk必然至少有因数a1个p1,a2个p2⋯因为我们要让s^k\%m1^{m2}==0就是说s^k是m1^{m2}的倍数所以s^k必然至少有因数a_1个p_1,a_2个p_2\cdots因为我们要让sk%m1m2==0就是说sk是m1m2的倍数所以sk必然至少有因数a1 个p1 ,a2 个p2 ⋯ 因此对于每个s我们将它依次除以前文得到的p1,p2,p3⋯因此对于每个s我们将它依次除以前文得到的p_1,p_2,p_3\cdots因此对于每个s我们将它依次除以前文得到的p1 ,p2 ,p3 ⋯ 其中如果s没有一种M含的素因数,这种情况就不成立其中如果s没有一种M含的素因数,这种情况就不成立其中如果s没有一种M含的素因数,这种情况就不成立 否则必然可以凑出因数a1个p1,a2个p2⋯否则必然可以凑出因数a_1个p_1,a_2个p_2\cdots否则必然可以凑出因数a1 个p1 ,a2 个p2 ⋯ 在成立情况下令s=n∗p1b1∗p2b2⋯(b1,b2,⋯均为整数)在成立情况下令s=n*p_1^{b_1}*p_2^{b_2}\cdots(b_1,b_2,\cdots均为整数)在成立情况下令s=n∗p1b1 ∗p2b2 ⋯(b1 ,b2 ,⋯均为整数) 三.求解三.求解三.求解 所以sk=nk∗p1kb1∗p2kb2⋯(b1,b2,⋯均为整数)所以s^k=n^k*p_1^{kb_1}*p_2^{kb_2}\cdots(b_1,b_2,\cdots均为整数)所以sk=nk∗p1kb1 ∗p2kb2 ⋯(b1 ,b2 ,⋯均为整数) 且sk是m1m2的倍数则kbi≥ai且s^k是m1^{m2}的倍数则kb_i\geq a_i且sk是m1m2的倍数则kbi ≥ai 在已知ai,bi的情况下,便可以求出k的范围在已知a_i,b_i的情况下,便可以求出k的范围在已知ai ,bi 的情况下,便可以求出k的范围 最后根据解集求出k在对于所有k取最小值可得答案最后根据解集求出k在对于所有k取最小值可得答案最后根据解集求出k在对于所有k取最小值可得答案 四.根据思路完成代码(小练习,代码在下面)四.根据思路完成代码(小练习,代码在下面)四.根据思路完成代码(小练习,代码在下面) ① A.x%a==0A.x\%a==0A.x%a==0 B.x%a!=0B.x\%a!=0B.x%a!=0 C.x/a!=0C.x/a!=0C.x/a!=0 D.x/a==0D.x/a==0D.x/a==0 ② A.b/cnt+(b%cnt==0)A.b/cnt+(b\%cnt==0)A.b/cnt+(b%cnt==0) B.b/cntB.b/cntB.b/cnt C.b/cnt+(b%cnt!=0)C.b/cnt+(b\%cnt!=0)C.b/cnt+(b%cnt!=0) D.b%cntD.b\%cntD.b%cnt ③ A.{i,0}A.\{i,0\}A.{i,0} B.{i,m2}B.\{i,m2\}B.{i,m2} C.{i,m1}C.\{i,m1\}C.{i,m1} D.{m2,i}D.\{m2,i\}D.{m2,i} ④ A.1A.1A.1 B.iB.iB.i C.m1C.m1C.m1 D.m2D.m2D.m2 ⑤ A.0A.0A.0 B.−1B.-1B.−1 C.m1C.m1C.m1 D.m2D.m2D.m2 五.正解五.正解五.正解 参考答案:BCADB参考答案:BCADB参考答案:BCADB 创作不易,求点赞创作不易,求点赞创作不易,求点赞

#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; }

#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); }

> 这题因该是普及+才对呀 【做题背景】数学题，秒杀！ 【算法名称】质因数分解 【算法分析】题目即要求最小的正整数 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<sstream> #include<algorithm> #include<bitset> #include<conio.h> #include<fstream> #include<iterator> #include<exception> #include<complex> #include<deque> #include<functional> #include<iomanip> #include<ios> #include<iosfwd> #include<iostream> #include<istream> #include<limits> #include<list> #include<locale> #include<map> #include<memory> #include<new> #include<numeric> #include<ostream> #include<streambuf> #include<queue> #include<set> #include<stack> #include<stdexcept> #include<string> #include<typeinfo> #include<utility> #include<valarray> #include<vector> #include<atomic> #if __cplusplus >= 201103L #include<array> #include<chrono> #include<condition_variable> #include<forward_list> #include<mutex> #include<future> #include<initializer_list> #include<scoped_allocator> #include<ratio> #include<random> #include<regex> #include<typeindex> #include<system_error> #include<tuple> #include<type_traits> #include<unordered_set> #include<unordered_map> #include<windows.h> #include<thread> #endif 注： #include<bits/stdc++.h> #include<windows.h> #include<conio.h>//万能头不能导入这两个头文件

题解

#include<bits/stdc++.h> using namespace std; int prime[3310],mx[3310],sx[3310],s[10010];//存下质因数，M的指数,Si的指数，还有所有的s bool isprime(int n)//判断质数 { for(int i=2;ii<=n;i++)//用ii<=n免去了计算sqrt(n)的过程 if(n%i0)return false; return true; } int main() { int n,m1,m2,tot=0,minn=1<<30,flag=0,np,ff=0;//tot记录质数总数，minn打擂台，flag记录某一个Si是否有结果，ff记录所有Si是否有结果 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++)//对m1进行质因数分解 { while(m1%prime[i]==0) { m1/=prime[i]; mx[i]; } mx[i]*=m2;//在这里就相当于m1^m2的操作 } for(int i=1;i<=n;i) { memset(sx,0,sizeof(sx));//每次清空si的指数的数组备用 for(int j=1;j<=tot;j++)//对Si进行质因数分解，由于m<30000，只需要判断Si是否有30000以下的质因数就行了 { //而且我们只存了30000以下的质数，用for循环判断prime[i]<=s[i]会RE 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; 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++) { 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; }