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

杨利霞

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

( O8 ?( [( o8 ?+ Q( a, A( H( _题意:  寻找有100个约数的最小数
/ Z# d  X5 X) n思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

代码:

& c) U2 W$ Z8 @% b" |) ]+ J/ |#include<bits/stdc++.h>
, a; D. h  n9 I! g& D#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
, O6 d) R; m6 B' _4 n6 qtypedef long long ll;
const int inf = 0x3f3f3f3f;
3 l, ]8 @5 ^% u) Qconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

/ f" D* M) E4 L6 S* L  p2 r+ @bool vis[123456];
vector<int>prime;
, v' w/ P5 \0 Y4 F$ i6 \' G
% [9 G# t- p6 C+ M; Ovoid init() { //素数筛
: |9 }; j  C" W( ?/ s  `    for(int i = 2;i<= 30000;i++) {
1 W$ N6 w& ?+ D        if(!vis) {
7 n! `+ ?4 Z. c$ s            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
        }
    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
    return ;
}
; P2 [* h+ E) |7 \- O7 r
1 P2 }7 M! {$ n+ v. K' X# ^int cal(int x) {
    int num[123];
  l9 |7 k3 N, A! F, z' Y+ ^    mem(num,0);

& @, [4 d/ O+ y4 A" r! E1 |! u    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
# _$ g/ `8 d3 E; {" t        if(x%prime == 0) {
            cnt++;
0 F& c- Q; N- ]0 h            while(x%prime == 0) {
                x/= prime;
% H- m; `% I' C  y                num[cnt]++;
- r- Y: f) ~! d0 l$ K1 n1 O% v            }
' \8 n: `/ \& u/ d! S; `) e        }
    }
    int ans = 1;
1 L* {* ^" F0 G: C    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
3 r1 Y. P. W1 G5 b3 ]    return ans;
}

int main() {
    init();
    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
; h% l: ^( |; X; S& i        }
    }

    return 0;
; `( R% v' K: j4 U( d" B( x3 O}
8 j( P& T: m5 I# u9 v---------------------
# o. x3 g2 T% z9 H/ y作者：nka_kun
来源：CSDN

- b; Y2 O7 v" U
) x0 ^2 m/ X+ M0 [
% q" R1 N- }4 Q& N0 F- e7 Q3 a