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

杨利霞

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

, ?- b; u+ V. ?2 E% e5 A
) W4 Q" a$ t+ b% R题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
  Y6 j3 p: L' G$ }9 S: x$ L3 S
7 q- M# b% Q) o4 S- _: }$ U结果:45360

3 n9 W6 \! E- h" @8 A% i代码:
, G1 ]2 k$ c! h7 H/ d% j, n/ b7 [
#include<bits/stdc++.h>
: G$ H  y$ F7 l. F3 _% x#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
( r( D1 X# @* `, F. Bconst int maxn = 3e5+55555;
4 K9 J7 M& p  q0 |9 n, Hconst ll mod = 998244353;
const double eps = 1e-7;
4 {( ]: l$ z. N; W1 [
bool vis[123456];
. R) x/ W% X* j- E* H" Rvector<int>prime;
8 f+ K# g& g7 w8 I+ t/ j/ |
7 V& _% ?, o: P# f( U$ hvoid init() { //素数筛
/ B8 r  W9 Z% y$ J3 \' ]7 P    for(int i = 2;i<= 30000;i++) {
% j- w* _  s- c0 k9 V8 Y        if(!vis) {
; t( c1 K3 y9 P- {' a' c8 J: {: K            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
% x4 W- N2 ]1 N0 j        }
    }
- |7 w8 @; I* P. j: ^8 \    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
; l+ w! J& K  Y7 N& |2 ?    }
. Z" E9 @4 N+ Q3 ?( e    return ;
}

" V# U% @$ r. ^( vint cal(int x) {
    int num[123];
    mem(num,0);
  O5 |" Z' G  K6 l  G8 M' A$ Q; g
    int k = prime.size(),cnt = 0;
' L4 z) k4 F; {/ f, f    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
: ^& M" j% d6 v) f; \            cnt++;
            while(x%prime == 0) {
+ K/ t  D' h3 [: p                x/= prime;
                num[cnt]++;
            }
0 A! x. x2 m- x8 Z0 I# z# R" L        }
    }
# h$ g, Y7 N# f4 U8 f9 c2 W) b    int ans = 1;
3 W7 z! L6 |" O, n. f7 m- q) y    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
4 B1 Z$ ]/ C$ p2 u% t6 H. C/ h9 Q    }
) T3 Y( B- C1 \6 c: x3 o    return ans;
}
8 ~* _0 Q: f0 E# H
( L8 O. r  X3 O3 Kint main() {
    init();
    for(int i = 99;i<= 1000000;i++) {
' D; I+ l+ B% ~( K+ l, Q0 u2 z        if(cal(i) == 100) {
& d) {; e& `* U5 n% {* n6 {8 u6 L            cout<<i<<endl;
/ Q! i% G4 D4 i% V            break;
0 P$ ]$ U4 |" x$ B' d# Q1 t        }
# q( J/ R8 e& e6 d    }
0 F4 A. ]. p$ E2 v5 Q1 i, ^
    return 0;
6 D7 L0 g$ X3 X6 B9 |( b5 r}
---------------------
作者：nka_kun
) e/ a: @5 B: x. W. Y( f* ~$ U来源：CSDN


( ~% H& ]9 A4 M+ [# S" t( E
+ C3 w. T/ g2 ?; _) ~