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

杨利霞

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

; q* }2 H/ g* T题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
/ b$ ]4 B) m0 b7 _; |
结果:45360

0 I3 g( n" L/ W( X4 f6 b代码:

#include<bits/stdc++.h>
( O  k/ J/ V& o8 h$ P8 O#define mem(a,b) memset(a,b,sizeof(a))
+ c% a# ^5 K1 j9 ~8 V" rusing namespace std;
% `# C: d& Y: f$ Etypedef long long ll;
const int inf = 0x3f3f3f3f;
1 n0 ^( v! s2 e3 z$ s9 F& gconst int maxn = 3e5+55555;
const ll mod = 998244353;
( |& [' W, S; _: c6 pconst double eps = 1e-7;

' b1 A2 [* D, K8 cbool vis[123456];
vector<int>prime;

void init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
+ j+ h$ l/ a$ H. c( F$ c            for(int j = i*i;j<= 30000;j+= i) {
( A' B9 P# P/ Q4 ], I: x* O                vis[j] = true;
5 x8 ?8 ^. z6 `' b) `' u            }
        }
# J! W6 U% F5 F4 F    }
5 A6 |4 Q  S1 I; H  `- r    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
: Q: E8 ?6 s" ~/ N( e    }
. J& S- T* ]8 I, p, [    return ;
}
$ q, f/ h* a0 U
# a+ W- S6 \  e$ A  ], Uint cal(int x) {
    int num[123];
) b" d9 Z) h# B4 Q2 ^% ?/ ]9 V( O    mem(num,0);
* u7 d$ M8 M/ }; K. z# R9 @
    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
( N  k" |: O' [- C4 ^        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
( A+ i7 T) a% c) O- a, y                x/= prime;
+ ^! m. \+ \; q' d) C* N                num[cnt]++;
            }
        }
    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
$ E9 k0 A2 O5 m5 W# D    }
    return ans;
8 O( X& Z- s) z4 x$ b2 ~}

! K5 @! G/ K6 q% cint main() {
    init();
* P2 Q9 j/ h0 l& }1 U5 l    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
        }
    }

    return 0;
}
* b+ T, s0 @1 Z6 R  P& r: j---------------------
作者：nka_kun
来源：CSDN

0 m# p/ x% {- E7 B' ~% a

4 \( x  F" s/ j