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

杨利霞

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

9 d5 y* r5 m4 q$ S4 p0 K
$ C3 Q- R' q; f+ n5 @题意:  寻找有100个约数的最小数
+ O+ |* O& a: X1 F思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360
2 S/ H' v9 R5 v. V3 {% p
; }8 `% b& n; G5 d4 x# J) A; _代码:

#include<bits/stdc++.h>
" Y0 D+ c2 ?: ~# ?. I0 x5 l" X#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
/ n+ j/ J: f) ~8 _const int maxn = 3e5+55555;
const ll mod = 998244353;
$ L3 ~9 C& Z/ u# a" C: tconst double eps = 1e-7;

bool vis[123456];
% q- j4 G( v; O/ v& y' J$ l: Tvector<int>prime;

" ?& w$ l2 f( z# ~  W9 R$ |void init() { //素数筛
  Q2 ?+ B, s0 A/ u9 v, |8 G    for(int i = 2;i<= 30000;i++) {
" W9 B( h; W7 W1 S4 O7 l        if(!vis) {
' o0 G2 Y: L7 j) N6 l, x" ~9 t            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
        }
8 q/ r1 o- F1 j/ n: t    }
    for(int i = 2;i<= 2019;i++) {
( W1 ]; I, i; v% f, R$ Y' W4 [: c# Y: X        if(!vis) prime.push_back(i);
    }
    return ;
}

: @2 Y7 F( S' F4 E+ A' M7 tint cal(int x) {
    int num[123];
3 H& Y2 R" s. J; i5 W* y    mem(num,0);

    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
  T: r3 n% F1 W2 ^        if(x%prime == 0) {
1 ~: |" R, f$ E% ^0 B            cnt++;
- N  ?& s& G# W; t9 s, d            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
7 c. c% P. x/ _% ?/ T2 t# H/ }5 m            }
        }
    }
" D8 P6 _* S9 p; q  i    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
: ?4 K7 l) [1 k    }
2 s1 `( t5 f1 z* h    return ans;
& p  n: Q0 a0 O. a% j$ r( y}
8 [4 s+ ^9 g+ H
1 v1 u# I, Z$ W  P5 \int main() {
! i) i& u$ u( R    init();
! W& x9 X3 N% K+ F5 C    for(int i = 99;i<= 1000000;i++) {
% R* f7 n, @5 b2 g  b1 w# _        if(cal(i) == 100) {
8 }0 y% [0 o8 W            cout<<i<<endl;
& F1 ^! O' ~1 y; l            break;
        }
    }
) m( S5 X) D! O% T/ [. w$ [
    return 0;
}
---------------------
作者：nka_kun
来源：CSDN
' ?1 L) a2 F6 [4 V" s3 g/ @

& S' m0 ?. R2 r8 V8 u