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

杨利霞

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

+ y* j- k' d3 S2 }: r* h- u
题意:  寻找有100个约数的最小数
1 ]: s) a+ n! n思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

$ K0 i! A8 a1 J" u* v9 I% k代码:

# q; l6 o7 Y1 M/ F7 z! g& f8 j#include<bits/stdc++.h>
- l! B- p5 d4 V#define mem(a,b) memset(a,b,sizeof(a))
4 H1 c+ Q) H3 X5 g# xusing namespace std;
typedef long long ll;
6 V0 Y% s0 K1 N: N5 Yconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
3 q0 @: E6 q2 W' T  `% j& _! O7 z: a" oconst double eps = 1e-7;
' X5 b/ }! b6 w9 @
bool vis[123456];
! ^6 k4 o/ n+ g9 P$ T* O/ xvector<int>prime;
5 V  C. X6 J' n! o2 m. |
void init() { //素数筛
$ S, M1 O2 V5 P& X2 ~    for(int i = 2;i<= 30000;i++) {
# l$ G% V+ e: R7 j8 @        if(!vis) {
7 }) E  k+ K( A            for(int j = i*i;j<= 30000;j+= i) {
- Z  s' |" J0 s, N2 f0 c2 G                vis[j] = true;
* ?9 _6 K  _- e! c            }
        }
    }
/ r/ N( _: s' L8 R    for(int i = 2;i<= 2019;i++) {
4 r, j7 b. }5 e, B7 M4 P" T        if(!vis) prime.push_back(i);
; t, ?3 b2 n' J# |6 T3 C& d- R( @( P    }
    return ;
}

4 J0 p9 k+ S9 f: O1 Rint cal(int x) {
    int num[123];
    mem(num,0);

$ Q+ a/ q8 F- d% r% w    int k = prime.size(),cnt = 0;
' W2 D' Q; g1 a# _! s4 O. G1 G2 Q    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
$ ^0 U# z4 B( s  |% o            cnt++;
            while(x%prime == 0) {
7 A# i; A0 q/ r' s- j                x/= prime;
                num[cnt]++;
            }
4 [3 d7 T2 ]* w) O; b        }
/ r; q( X9 o, t    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
    return ans;
: ?; c6 K2 R1 L8 g7 F: ]( Z6 R}
' k& D3 d# l/ I" T' E( x
int main() {
    init();
- W  h" M7 S( h- L    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
" \9 L  i& F* _3 I8 t        }
    }
& y. b5 Z0 p. d: E$ ?1 e
" Z! s# }& Z- E    return 0;
}
---------------------
: o, x4 O( o9 K  U, v! q1 b作者：nka_kun
来源：CSDN
  [6 T/ h' B- j
! x; z* m6 g- V- f" `  `4 d

" c) f) L9 n# i! l+ U