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

杨利霞

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

9 u! F9 [9 d. S  ~题意:  寻找有100个约数的最小数
# _5 B$ P" X2 F思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
! s* R4 b4 {2 s0 d( j
结果:45360
7 A/ d( b, U7 b; z' y
代码:
& \- _4 M. s5 y8 i
. I7 j' Q+ R4 w. b#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
; O0 v+ j" L) _3 r0 G/ \using namespace std;
4 r$ B9 m. K9 \: d' \typedef long long ll;
3 O8 k( Z/ S2 G, Z- bconst int inf = 0x3f3f3f3f;
7 n% c  J: m: f8 m+ Xconst int maxn = 3e5+55555;
& ~0 o: I! h( A1 bconst ll mod = 998244353;
  s. M% w) \1 N* sconst double eps = 1e-7;
( h( ^8 g- X3 l. k& w% U+ F; U
! q: P+ _9 D( c) _/ x1 Zbool vis[123456];
vector<int>prime;
1 J* i' Z0 z3 y! N
* a* y+ _1 l/ k8 ]& bvoid init() { //素数筛
, q" @5 u3 N$ ?1 ]- S9 @- D, d    for(int i = 2;i<= 30000;i++) {
* C4 l  G/ j% @: @& F" _9 n        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
: H/ l/ a. E, `  J2 [! A" A            }
0 n4 {( c# {+ O' @8 q* ]$ V4 M        }
- O5 c( {6 w: t: ~    }
7 g; ~( }. J% i0 B    for(int i = 2;i<= 2019;i++) {
9 ^/ {  O7 k4 {/ P- y/ p        if(!vis) prime.push_back(i);
+ m- [  T2 N/ U    }
: I7 h- Z- |/ e    return ;
; j. k' Y! V0 J3 K! a3 l}

0 }) ~# H/ F3 J; R: S* Tint cal(int x) {
    int num[123];
2 [4 c! m/ m3 J    mem(num,0);

    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
, |% n. n0 y5 ~        if(x%prime == 0) {
+ g1 t6 t9 [/ n            cnt++;
$ c; a& q% L/ Z) ?4 N            while(x%prime == 0) {
5 _0 w: A7 r7 R3 |                x/= prime;
                num[cnt]++;
            }
! g3 ^7 [& ~8 o1 f' ^- n# V        }
* U2 |6 M4 q% v9 U& x    }
    int ans = 1;
( f+ Z  ~5 h3 p$ ?' M7 E- m$ \    for(int i = 1;i<= cnt;i++) { //计算因子总数
+ |* r7 G6 c8 T5 A! E, e        ans*= (num+1);
    }
    return ans;
: f; H6 c% ]$ L: f- O- _! P5 h}

int main() {
1 C/ @+ J* x( \  F" e* a' a    init();
    for(int i = 99;i<= 1000000;i++) {
* |# T6 }5 B* ?3 w# [; z) z        if(cal(i) == 100) {
            cout<<i<<endl;
6 M8 I) [  j- M0 R2 ]1 d: o1 F            break;
5 ~' b1 Y2 d6 |" P( \  T( p% D0 P        }
; ?4 P2 h& E! p$ e    }
) `+ @/ a4 N3 A4 S
    return 0;
. o0 I" W' q) X- X}
---------------------
作者：nka_kun
  P# ]% _; k3 X' N7 l来源：CSDN


( W) X" o& e; R8 @( I/ I" j