查看: 2117|回复: 0

2019第十届蓝桥杯B组决赛题解第四题

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 15:53 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

2019第十届蓝桥杯B组决赛题解第四题

题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[123456];
vector<int>prime;

void init() { //素数筛
for(int i = 2;i<= 30000;i++) {
      if(!vis) {4 Y4 b8 m4 p) V0 R
         for(int j = i*i;j<= 30000;j+= i) {
: o4 i7 U2 ?' y% K5 {! {             vis[j] = true;1 \7 E/ t* T- d6 Z: [
         }
# Q& A0 P/ H4 ]       }
- L; G( K  m+ E; ~ }( a6 A0 G$ k, N& N+ B
for(int i = 2;i<= 2019;i++) {
& C  B- S: q& }1 S       if(!vis) prime.push_back(i);$ a6 A) r- I& r3 `$ `( U
}$ H  C$ _& X3 y- N, F# x
return ;
" |' e0 V& ^  W' v" S1 h; Z}  T- @0 `% |) T0 K, g

1 q5 z& v2 v% H% p6 Wint cal(int x) {
* R: o3 \$ w- ]! q, A int num[123];  p- s1 I4 i/ ~3 q0 }( L: p, C9 M
mem(num,0);9 N  a5 s# U* j% ?0 G2 b% z

7 `3 D9 q. _! A3 y int k = prime.size(),cnt = 0;, P7 y/ w. a9 E
for(int i = 0;i< k;i++) { // 分解素因子5 Z, q  r1 i# u
      if(x%prime == 0) {
# L- H4 X- G' B          cnt++;3 B1 p( K9 K' l9 f5 }5 k
         while(x%prime == 0) {
3 d0 g1 i, Q& A0 [  o             x/= prime;, O: M4 I2 O1 Y; [5 q4 _
            num[cnt]++;4 F! d( A; ?( @% h7 _
         }
# K! y* X% B$ o       }
2 s' y, f8 c6 e3 J. u$ P0 g }! i6 ^/ j) W, a  `" z
int ans = 1;
  E( U- P8 L. H" U; z6 P for(int i = 1;i<= cnt;i++) { //计算因子总数* P# @/ ~8 G3 I
      ans*= (num+1);& A) p# _$ ?# k/ }" h
}) I5 D0 D6 M( W' R* t. j. k, K
return ans;
  w4 r. O( q4 @}$ k1 ?( q4 e2 \$ u
+ q3 k8 Y$ Y/ E3 X5 e
int main() {4 t3 ^6 v0 v2 o/ w
init();3 V8 M; N& f' V7 R$ ~
for(int i = 99;i<= 1000000;i++) {
2 c, W  @  o- F' O1 {" z) U) k8 k       if(cal(i) == 100) {
3 F9 L( ^4 `& h$ v# C7 n& o          cout<<i<<endl;
, o2 b0 V8 H" G% g; ?% W  m          break;) S' x+ I3 \6 U  u  K
      }7 N8 B! \, |3 Q
}
" G: l' `; p/ L# y8 }4 a+ [
: X/ g% L4 G) E  T1 g7 t# ], d5 B return 0;
4 w% R, t7 d0 E- Z8 z1 h}5 h7 {' {7 w5 _9 g
---------------------
5 q' s* P9 F% Q0 Q% C) ~1 p# Y; M作者：nka_kun
: t) b2 F6 r0 g6 z$ e来源：CSDN 7 ]2 M+ _4 x  g- D! {# G

8 I8 o& ]3 f5 U$ k$ S+ i% C
( ]; ~: e% [5 `$ M  l6 O% Z3 i
3 I4 |1 u. ^3 ?: ?. Q3 p