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

杨利霞

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

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

结果:45360

* s% m" }( X  ^' f; i代码:
5 [: [  h6 G; T1 s0 V
#include<bits/stdc++.h>
+ ^3 K7 k1 {  |& ?' a  K#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
! O. N. @& U% S& B4 W2 \6 [0 Uconst int inf = 0x3f3f3f3f;
) H$ |3 g% S( t" j' N9 b7 o# t4 X5 x% uconst int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;
+ ?; j# E8 X& ~& G) G* W
bool vis[123456];
6 G9 L5 y" M6 vvector<int>prime;

4 A7 Q; d; g8 uvoid init() { //素数筛
# ^  J, w' N4 U9 C    for(int i = 2;i<= 30000;i++) {
" {7 O( Y" s4 i        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
. U3 z; h  V8 U$ G+ W. L4 ?, t            }
        }
    }
  L/ ]! ~, x/ k" ]7 `& ~0 t    for(int i = 2;i<= 2019;i++) {
/ S0 \8 |& d( c" n; h        if(!vis) prime.push_back(i);
    }
% s: n  o5 A1 x7 y8 d' r    return ;
}
0 n: p; g9 n1 j+ [. d# a
& v& t. S5 Z9 H  J( g% Qint cal(int x) {
    int num[123];
    mem(num,0);
4 i. A; I* P& c* [/ V9 J
    int k = prime.size(),cnt = 0;
* f. {: c/ k: a0 u( r! B    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
            cnt++;
; D; M  V) q( L8 ]- {0 M            while(x%prime == 0) {
                x/= prime;
" z/ {% q; c  W. y$ e                num[cnt]++;
            }
4 t4 q1 r' k5 x: R; ^4 H9 g" L        }
    }
1 d+ w9 S7 l% t8 x    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
8 F5 G" g1 [* J3 X. V/ a0 X    }
! @! }6 N- p: p; o0 v+ S& X7 R$ A    return ans;
6 _9 R1 n% z, t- \4 |}
! e) s: x; G0 T  G
int main() {
% y6 O) I1 @; `# Y" j; h    init();
    for(int i = 99;i<= 1000000;i++) {
' `( p$ ^& n9 }        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
' g; `6 _, v; ^% F- A! N8 b        }
    }

1 P9 C/ ?+ V7 Y0 b  {) c    return 0;
9 v' D1 e& M$ m+ c, y$ `9 ]) p0 A}
---------------------
作者：nka_kun
- k. f, {" F( W* S5 a. T来源：CSDN



9 |: n+ N1 a! {' @/ ]& Z% I