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

杨利霞

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

0 J& I" J8 T8 C+ C6 I. R
+ Q' h  E8 b+ Q' h3 g: u2 l4 L% J" N9 S题意:  寻找有100个约数的最小数
# n) G0 u" z" f* U* e: d$ c) Q思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

代码:
( H  c  A& ?0 i+ |8 A3 B
7 Q0 l0 A) {9 K% m8 t4 {1 S#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
7 u% W- ~( u+ T% N+ E! q) R' yusing namespace std;
3 M2 x; M+ A) u( Ktypedef long long ll;
( |6 [" U( ?4 H, P4 o- d5 Q+ i2 h: Aconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
& m' K- g& i3 Q, l# Rconst ll mod = 998244353;
const double eps = 1e-7;
: T: f' C, A0 \: K9 |5 `3 h
1 t" F) S  K! m5 p$ n* `. e7 L: {bool vis[123456];
: u8 v+ t. A# `. Svector<int>prime;

void init() { //素数筛
+ Q; P& ]4 i' U6 O0 h# H    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
$ ^" G. W" o, g  B            for(int j = i*i;j<= 30000;j+= i) {
0 H9 E' H! i& H' o' l6 I' H3 W                vis[j] = true;
" y/ K4 d9 B) C/ r( S- H2 S; ~5 {            }
        }
2 R2 r3 M9 h; h    }
    for(int i = 2;i<= 2019;i++) {
3 T9 H2 ?' Z& x- n- P        if(!vis) prime.push_back(i);
    }
' R- G& {: H  G0 ~4 Z    return ;
! z9 i" j7 ]1 j# q; B/ N' \}

7 x  a3 e- t: Q) b- j. ?int cal(int x) {
8 j+ X0 p) \* [1 J+ ?+ x& Y    int num[123];
% Y0 u2 c3 J* ~    mem(num,0);

3 Z7 Y( N) B/ d    int k = prime.size(),cnt = 0;
! J: b8 J- q7 c# h' |( }    for(int i = 0;i< k;i++) { // 分解素因子
8 V/ @5 r2 \4 j        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
                x/= prime;
' @' Z% \- s0 X" o+ Y0 A                num[cnt]++;
) O& ]) x8 a& H5 E# G- p& \            }
; i' s2 k0 ]. h: B" e        }
    }
    int ans = 1;
: x' `) p& n( j- h+ l" t    for(int i = 1;i<= cnt;i++) { //计算因子总数
( M3 `& Z/ l" ]        ans*= (num+1);
& i/ v- d  |# A6 j; [# A    }
/ ?% y9 S, n4 z0 Y  {    return ans;
# B$ K3 w% X4 p" ~}
: M. d0 l' ~5 e. {! \* K, v
2 |' t# x" c7 g  L# yint main() {
% u# m4 s0 Z. x: |    init();
. s" V) Z2 I& L8 T    for(int i = 99;i<= 1000000;i++) {
1 t1 n- V6 _* H% ^* M        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
        }
    }

7 l2 r8 d' f. L7 M0 F    return 0;
}
---------------------
9 v1 p# Q: G8 W8 t' b作者：nka_kun
9 G7 a# B9 }, ]) U# G% w来源：CSDN
8 e7 ^4 D& |7 a6 D, u. b8 C
" P; X3 K! B1 `. ^

; b" p: y  K4 Y! B9 q8 _