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

杨利霞

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

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

1 [& E1 Z# X% }结果:45360

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
  L7 |8 L' Z5 a- ]4 J. ]using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
8 X5 }8 q. K  H" i9 P( s5 u1 ^/ Hconst double eps = 1e-7;

bool vis[123456];
vector<int>prime;

# K  \$ W' t9 ?! C8 Uvoid init() { //素数筛
. {5 x8 i7 B$ _& W5 b    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
' o  A5 f1 v8 W/ U& C6 V            for(int j = i*i;j<= 30000;j+= i) {
% _+ C  g* U' W, ]                vis[j] = true;
% z/ @  J! v0 p: n0 k            }
        }
    }
    for(int i = 2;i<= 2019;i++) {
, R; t  H# ~, I( r& w        if(!vis) prime.push_back(i);
    }
    return ;
}

int cal(int x) {
% a/ T" s$ u9 r) @) g    int num[123];
1 ^, A6 f" u$ z9 u4 O9 y    mem(num,0);

7 A$ {+ C2 d6 R    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
1 j* U3 R- [/ R: s* G            cnt++;
            while(x%prime == 0) {
) P) v4 a3 G' N2 x8 v, N, Z                x/= prime;
                num[cnt]++;
            }
8 h3 D( A4 G6 O( K% A9 T        }
8 J$ K! x8 J, s6 [+ Y    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
2 }! U( ?4 _2 i, k) B) u        ans*= (num+1);
9 l) T" c$ L. q* F# W: F    }
3 Q) s" y5 E- Q: p7 f0 D, a    return ans;
}
  w! V. F) D' c0 K/ f" J2 E
int main() {
    init();
: \% ]8 P1 j2 s0 [- s& {4 R    for(int i = 99;i<= 1000000;i++) {
2 @. l1 N! ~5 Q; i' F        if(cal(i) == 100) {
4 \9 y7 \; N3 F. t' q3 R6 `            cout<<i<<endl;
( [' v# p2 ?9 o* H, v            break;
        }
& {, H4 h6 o" t. G    }
+ {; b  `' `2 b3 f2 l  U+ m( s; U
1 \8 y3 n9 U2 @    return 0;
}
---------------------
作者：nka_kun
" U9 w; h0 l+ a0 M; U来源：CSDN

: v4 }' e$ |+ n
( q4 b  _- x+ \0 R- j" C
5 [- C  b* s& F+ F0 a