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

杨利霞

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

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

结果:45360

# a, }! b# M+ @# q代码:

. ?2 y( X1 ~& X. [5 k) Y. t" Y8 z3 W#include<bits/stdc++.h>
% V9 B) g* ^- x" H, d#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
9 V% @  J# ~0 b0 Q; m# b  b  rtypedef long long ll;
const int inf = 0x3f3f3f3f;
5 B6 j/ `2 ]# ?: B; Q) ^2 ]. Cconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[123456];
vector<int>prime;
+ z) X- D0 r& Z9 }: ^! |
  T# w" g8 b0 e8 L8 ^  _void init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
  o2 Z5 G9 M4 y* Y        if(!vis) {
8 K% x# u1 ~  ~8 Q% c3 M* b            for(int j = i*i;j<= 30000;j+= i) {
  A1 c, K! T2 o2 e                vis[j] = true;
            }
: C0 H. U( ]% G& W9 f        }
" R- Q3 G/ W* W' J% K6 U    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
6 S( j, o! J4 r6 B3 T1 q    }
+ P5 d; L% u4 P+ E" m1 q    return ;
}
% q/ [, `" q1 _! p1 _6 W
int cal(int x) {
& Y6 A3 a& F; S% F4 ~    int num[123];
3 {4 r( ~0 ^  B$ ?0 c+ ?5 b    mem(num,0);
9 d$ O/ L7 T- x! x
    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
# ]8 I5 a; \1 w+ }0 n- q        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
            }
) }; D2 O, D$ a* F7 N& m% Z: P        }
    }
2 P' W3 P- c" D2 Z& I    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
; i# A, q6 J4 _    }
    return ans;
1 z$ Q7 J' S! s6 o9 G8 p}
0 n  q4 q8 ^& j: D
int main() {
    init();
) F* \$ {7 u' A" A    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
( ?2 B9 M' _) I1 Z            cout<<i<<endl;
6 }0 u2 A8 O2 d            break;
. ?. y: x. k  a3 A. Q        }
. Y  K6 l7 Z" H; S0 g; o    }
' M8 b& s1 r- t3 _
5 c- o# t# h! Z& T  a: L8 ~+ p    return 0;
4 c2 K9 V& U6 G4 {8 l! x& M( O}
1 K% K; {" x& }3 y7 [1 w---------------------
作者：nka_kun
# d. M6 W" s$ v- T2 @3 ^6 D来源：CSDN