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

杨利霞

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

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

/ M2 W/ _* ~4 H  L, ?! ~结果:45360

7 z5 z: \7 V2 L  ~6 a代码:

% l( K  _9 _( b: U' M' E, L, s#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
' J# i, E' t* A$ Iusing namespace std;
- k- f* r: I- M; htypedef long long ll;
7 c4 T; R; ^5 M6 _& ?" [const int inf = 0x3f3f3f3f;
2 J2 m$ k8 a4 Z; h3 o4 Z0 t/ G2 uconst int maxn = 3e5+55555;
const ll mod = 998244353;
# P* }; E& S) C* N. r5 Hconst double eps = 1e-7;
* B$ ]$ {- A- _  d% ^3 w. C5 f) {( I
3 w; O# o, K# s! g0 ^bool vis[123456];
vector<int>prime;

8 G' o2 |2 ^2 R* @: Evoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
& K+ W6 i3 n6 _$ i% h. c" Q3 Q        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
$ G/ D4 w; q" V2 p! H6 ]        }
' r3 z& \* ]5 u    }
$ |+ f! o/ T: J0 L7 S# t    for(int i = 2;i<= 2019;i++) {
& O5 h- R! x& K5 X8 v0 }% x/ R        if(!vis) prime.push_back(i);
    }
  ~  i9 Q  x4 v; T    return ;
}

, f' t+ G+ N. f& zint cal(int x) {
    int num[123];
8 z3 ]$ d7 E  p- H# m: Y4 T    mem(num,0);
$ V* N! J' w' T& m+ ~' H
    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
1 G& F6 V; k5 X9 C1 V        if(x%prime == 0) {
) H7 A; m- M% ^            cnt++;
7 }: Z) \7 N: d4 O. Q% y' |$ \            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
2 A: _' i0 S) V8 Z            }
2 m2 D5 c. J; b! |5 {0 t4 T        }
    }
/ q4 x. _! w( E, c, u8 s    int ans = 1;
' W! h6 l+ q; w    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
6 Q& n$ Z4 A# B9 L; K    return ans;
9 q  |$ |& q" s. j1 g. j5 P}

int main() {
' {) F" G) C! G5 R3 w    init();
3 Q1 w8 R& I% K9 a7 {1 Q    for(int i = 99;i<= 1000000;i++) {
8 j- P, A6 c+ Z! v& P- o/ U        if(cal(i) == 100) {
            cout<<i<<endl;
; q7 e2 a' p1 y7 j' G4 Z            break;
        }
' Z3 R1 K1 O* I2 o8 V. y- c    }

    return 0;
}
---------------------
% o& p! G! H( _% q& b3 U4 X" g) `作者：nka_kun
来源：CSDN
) X' t% c! W( e8 U8 R! q2 p$ [8 w
1 b  ^3 R! w+ z5 ~1 C
4 A" o* N! O% H) J4 x: N+ q
5 z8 a% R) Z4 j  |# o- ~' |6 g