质因数分解

题面给定整数 a,b如果 a%b0则称 b 是 a 的因数。现在给定一个整数 n计算整数 n 的阶乘的因数个数。输入格式:一行输入一个整数 n(1≤n≤50)。输出格式:输出一个整数表示 n! 的因数个数。输入样例:5输出样例:16题解 分解质因数 唯一分解定理唯一分解定理任何一个大于1的整数n都可以分解成若干个素因数的乘积如果不计各个素因数的顺序那么这种分解是唯一的n p 1 a 1 p 2 a 2 . . . p k a k np_1^{a_1}p_2^{a_2}...p_k^{a_k}np1a1​​p2a2​​...pkak​​n的因数就是这些素因数组合根据乘法原理c n t ( a 1 1 ) ( a 2 1 ) . . . ( a k 1 ) cnt(a_11)(a_21)...(a_k1)cnt(a1​1)(a2​1)...(ak​1)1因为有不取该素因数的组合情况nint(input())a[0]*51p[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]ans1foriinrange(1,n1):xi# 分解质因数forjinp:ifjiorx1:breakelse:whilex%j0:x//j a[j]1foriina:ifi0:ans*(i1)print(ans)相关例题十一届蓝桥B组C题mapint,intm;vectorintp;voidfind_p(intx){//欧拉筛stl版本m[0]m[1]1;forr(i,2,x){if(!m.count(i)){p.push_back(i);coutiendl;}for(autoj:p){if(i*jx)break;m[i*j]1;if(i%j0)break;//i能筛掉的已经被j筛掉了}}}inta[110];voidsolve(){intn100;find_p(n);forr(i,1,n){intxi;for(autoj:p){if(ji||x0)break;while(x%j0){a[j];x/j;}}}intans1;forr(i,1,100)if(a[i]0)ans*(a[i]1);coutansendl;}十三届蓝桥杯省赛A组 数的拆分结合分治 用数据范围卡找质数的范围质因数分解a x 1 y 1 x 2 y 2 ( y 1 , y 2 ≥ 2 ) ax_1^{y_1}x_2^{y_2}(y_1,y_2\geq 2)ax1y1​​x2y2​​(y1​,y2​≥2)可以看作两个桶定y 1 y_1y1​为偶次幂定y 2 y_2y2​为奇次幂对分解后质因数p y p^ypyc为1放哪也不行输出noy为偶直接乘入偶次幂项y为奇设定y 2 ≤ y ( y 2 3 ) y_2\leq y(y_23)y2​≤y(y2​3)先把一部分乘入奇次幂项中y − y 2 y-y_2y−y2​为偶数乘入偶次幂项但是筛1e18很大需要分大质因数和小质因数发现p y p^ypy如果y yy很大那么底数p pp就必须很小。如果y 2 y2y2平方底数p pp最大可以是10 18 10 9 \sqrt{10^{18}} 10^91018​109。如果y 3 y3y3立方底数p pp最大可以是10 18 3 10 6 \sqrt[3]{10^{18}} 10^631018​106。如果y 4 y4y4底数p pp最大是10 4.5 ≈ 31622 10^{4.5} \approx 31622104.5≈31622。如果y 5 y5y5底数p pp最大是10 3.6 ≈ 3981 10^{3.6} \approx 3981103.6≈3981。注意看y 5 y5y5的情况一旦底数p 4000 p 4000p4000那么p 5 p^5p5就已经超过10 18 10^{18}1018了。这意味着对于所有大于 4000 的质数P PP它在10 18 10^{18}1018范围内的指数y yy只能是 2、3 或 4。我们就不需要用循环去除法试除法去处理它们了直接用开方判断即可。所以我们将问题拆分为两部分小数部分p ≤ 4000 p \le 4000p≤4000指数y yy可能很大比如2 60 2^{60}260无法通过开方判断。策略必须用试除法筛法循环取模把所有小质因子除干净并统计指数。代价4000 以内的质数只有约 550 个运算量极小完全可以接受。大数部分p 4000 p 4000p4000剩下的数tp只可能是1 11、P PP、P 2 P^2P2、P 3 P^3P3、P 4 P^4P4或P 1 × P 2 P_1 \times P_2P1​×P2​。策略直接对剩下的tp进行开平方、开立方判断。原因如果tp是合法的它一定是个完全平方数或立方数如果它是个一次方的大质数或两个大质数之积开方检测会失败constintN4000,M1e5;constdoublePIacos(-1);constlonglongmod998244353,inf1e18;vectorintprime;voidfind_p(){vectorboolvis(N2,0);vis[0]vis[1]1;forr(i,2,N){if(vis[i]0){prime.push_back(i);}for(autop:prime){if(p*iN)break;vis[i*p]1;if(i%p0)break;}}}voidsolve(){intx;cinx;if(x1)returnno,void();inttpx,fg1;// 分解质因数// int tppx;// forr(i,2,x){//超时// int cnt0;// while (tpp%i0)// {// cnt;// tpp/i;// }// if(cnt0)couti cntendl;// }for(autop:prime){if(p*px)break;intcnt0;while(tp%p0){tp/p;cnt;}if(cnt1)returnno,void();}// 此时剩下的tp是4000的因数组成的// 判断是否为二/三次方intsqsqrt(tp),cb1.0*cbrt(tp);if(sq*sqtp)returnyes,void();else{// 邻域检查double存储精度问题 精确表示的整数范围大约是10^16 开立方根后 根可能比实际的根略小while(cb*cb*cbtp){if(cb*cb*cbtp)returnyes,void();cb;}}/* 一开始的写法 int sqsqrt(tp),cbcbrt(tp); if(sq*sqtp)fg1; else if(cb*cb*cbtp)fg1; */no;}