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

杨利霞

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

% h8 i6 A' ^' }8 P8 ~( p7 _题意:  寻找有100个约数的最小数
! R1 \% l+ r5 b% v- m思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

* K0 Q6 W6 L% p2 U6 ~# w2 y结果:45360
9 ~- M8 T  r+ e" U
代码:
6 G- F% _6 m, s! `
#include<bits/stdc++.h>
" Z% o; F4 R- p: q1 T#define mem(a,b) memset(a,b,sizeof(a))
5 H. Y1 N. ~; a  z  P7 rusing namespace std;
' r6 E) U* F' s. ~* Ztypedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
0 z- C/ I# |+ y$ vconst double eps = 1e-7;
: c: a+ P9 r( n; H6 q* y
7 }$ d+ T" w, n; Abool vis[123456];
vector<int>prime;
; t3 H4 C. h* z
void init() { //素数筛
. Z$ a3 C% Q# ]4 C# F    for(int i = 2;i<= 30000;i++) {
8 N" y$ C; h# V3 W1 V* A( x, h* h; N        if(!vis) {
$ q  a+ o# t& p+ y+ v  k9 T            for(int j = i*i;j<= 30000;j+= i) {
6 Q, Q2 o. Y) D/ Z. }                vis[j] = true;
1 I+ X( t7 H6 N; r( \5 b            }
+ t2 i  j: K8 }, F( q        }
* I' w! @/ o3 [0 j8 c% y& u+ m: ~    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
) k3 Z7 F% D# j% b( l    return ;
, g5 G( U; l* R9 v+ j/ g}

int cal(int x) {
    int num[123];
    mem(num,0);
! j- P: ^7 f9 z1 R
    int k = prime.size(),cnt = 0;
( A0 Z* x* u7 S9 Z* Y: X8 S7 h! j; d    for(int i = 0;i< k;i++) { // 分解素因子
/ ^8 y$ E2 w& p' H$ v. i( X7 u        if(x%prime == 0) {
" K& P0 y1 Q2 `7 p            cnt++;
' z. B$ H* Q+ j7 Q9 A            while(x%prime == 0) {
                x/= prime;
3 v. |( Q  X# o8 r. D! ~1 J                num[cnt]++;
            }
, e8 ~4 `5 d  f% [        }
5 G$ P% h( m2 n% s; }  ]$ [! X    }
    int ans = 1;
+ ^, S& j" C# V0 b    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
7 ]  V' J; ~4 F3 I. R4 M# b    }
1 ~# m' o% B+ R( d2 Y    return ans;
2 @& ]! y2 N4 F6 D' K3 H7 c$ ~}

int main() {
& K( X5 E  o6 Z- Y/ t    init();
, q5 z2 l" c) \0 j) m) u7 {/ a' O" ^* d    for(int i = 99;i<= 1000000;i++) {
: Z8 i3 m! p$ _        if(cal(i) == 100) {
            cout<<i<<endl;
( U* E% {8 Z/ D- H/ Q9 P8 ~1 k3 Y            break;
0 @# {3 I7 Q3 V  {2 W5 S' K        }
4 }/ y& U4 b: S7 v' l    }

    return 0;
( D# t. X6 l0 h# r& O0 g. c}
---------------------
作者：nka_kun
来源：CSDN