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

杨利霞

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

- p$ ^- H! ]7 Q, P* Z5 X
题意:  寻找有100个约数的最小数
/ X) s. O# g1 Y思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

代码:
; y; r& Q6 d, \5 j* R
. G6 ~7 t1 k* \7 c#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
# u7 v! Y, m( ~5 Pconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
4 n4 S! m, N* P9 C& S+ {- Uconst double eps = 1e-7;

bool vis[123456];
vector<int>prime;
) C- P" I2 E) |0 K3 y* o3 y$ P& B
3 i8 B8 r) Q& {* @3 b# M4 q: B( Fvoid init() { //素数筛
4 A7 L) p3 {9 e! y" }5 q" }    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
) F1 d" M# I0 r            }
* ]+ w( i, _+ Q( S- r& s1 A        }
; A0 k/ N( P3 x& e- B! j    }
" {( s2 }& B7 N9 o" o  n/ v    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
3 r  _" J! R, m$ ]    }
) r6 A( g. P/ u    return ;
}

int cal(int x) {
    int num[123];
/ k/ p+ L* P/ d    mem(num,0);
% y& ?' j  Q2 E; {& ?) v
2 V+ H: r9 V* L$ n+ `    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
; r& ?" h$ b# \2 a            cnt++;
            while(x%prime == 0) {
7 N$ n: S/ D! w% x- F# d! I                x/= prime;
                num[cnt]++;
3 f6 B: N9 h4 t9 L            }
        }
    }
/ D* y. M/ C& A+ i7 S0 V) f    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
8 y7 ~" e+ j* `. e% d    }
    return ans;
}

int main() {
0 f. `: U; u8 g" [% h5 J; F$ m    init();
    for(int i = 99;i<= 1000000;i++) {
1 y. @8 f. l( o        if(cal(i) == 100) {
3 c+ g4 K7 v7 S; K3 A5 ^) }+ C2 N            cout<<i<<endl;
            break;
) |9 d+ j% I0 E/ C        }
% T+ Z( z2 W0 |. }2 C1 H2 B) B    }

) |' S& O, V4 w% q- u6 I4 g    return 0;
7 n& H& z# f% p$ P2 D}
---------------------
0 h- {& a) |" s! a& y作者：nka_kun
来源：CSDN
+ ^1 v( Z5 F& G3 I" g& ~

3 F9 C3 T$ k. P5 q. P
4 }, d! m* y2 Y! ~8 W* {) [, I4 {