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

杨利霞

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

$ x: n4 v4 `! u3 D9 {  z2 k3 C
题意:  寻找有100个约数的最小数
3 \, O9 ]+ ?4 ?* g  T4 i3 o思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

6 s( K& N* S5 R1 d: `8 z3 G结果:45360

8 d* P9 a5 j7 @3 u- X代码:
% _/ q6 A# i* X* e0 V$ d
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
+ f2 H! }" M& ?  l; [using namespace std;
typedef long long ll;
% B; S# l5 ^1 r. C) P( b1 xconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
' c$ a0 g* G  S+ D: C& j. h7 Nconst ll mod = 998244353;
9 y( h7 F& @2 U" \const double eps = 1e-7;
6 C1 u# i6 Q4 Q
bool vis[123456];
vector<int>prime;
% V5 V" o- k3 B9 E8 R2 K
: G+ V7 s. W+ H- `void init() { //素数筛
" h9 P7 P( v7 C. a$ s" L% ]' J  s, |0 R    for(int i = 2;i<= 30000;i++) {
5 }( @# M+ D! t8 _0 |$ m        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
: X0 \0 c& s) P1 b% v& y& C                vis[j] = true;
            }
: W! ~9 h' r8 S  l# m  n0 g        }
6 B1 w5 t( U1 ]5 U7 A; l    }
    for(int i = 2;i<= 2019;i++) {
8 ~6 O8 e' G% V        if(!vis) prime.push_back(i);
    }
* j7 @5 }4 j' U. ]8 N) C( K    return ;
3 W' m) Z$ P& [) h5 I6 a& j3 T: ]}
4 x; }8 b# ^6 _% G6 ^' O
int cal(int x) {
# _! U5 G0 `* U7 K- C+ l    int num[123];
    mem(num,0);

; c# |) F4 s& }: R: m2 M# G) X    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
. y3 |3 u8 q! K            cnt++;
# U' I9 Y$ C. o1 ~- ]" {            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
3 v3 f3 c# l9 p+ s- p            }
        }
    }
    int ans = 1;
1 O* N8 W/ j9 M8 [" J0 |; W    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
5 ?7 i, s- A) ~/ b2 c8 ]! B    return ans;
}
4 {$ i# }) h# D5 |7 F9 _$ B2 a# ^
3 s# Y) o. }; |) `1 G3 Jint main() {
9 n! r' A& \3 A$ W4 f    init();
    for(int i = 99;i<= 1000000;i++) {
: i- r9 n- L8 e+ p        if(cal(i) == 100) {
            cout<<i<<endl;
            break;
9 @& P, K- O/ ^$ `9 U        }
  M( X% L' q) ^    }
) W- U( h, j) N: J! g
    return 0;
. d: @2 c# C( N8 T6 h9 L) p}
---------------------
作者：nka_kun
0 h5 J8 U, b( A' D# E9 l来源：CSDN


; G+ }5 ?) J" I( o