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

杨利霞

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

题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
1 P  e2 R& a) e* [+ d. i: \
结果:45360
( K# d& w' @- o* s( C, i! h
! K7 U! A9 p3 p% D/ i5 F& R代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
* \+ |; M8 I4 B7 husing namespace std;
3 e5 m7 E8 B2 |, rtypedef long long ll;
3 c  C: J% f4 z, Q1 X, s  oconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
7 j& V/ \" W8 Dconst ll mod = 998244353;
* P! S: y4 Q9 m' z2 qconst double eps = 1e-7;
0 [9 A: G) f% W- S& B1 J. W
bool vis[123456];
: W# u" h# J- c! ^& mvector<int>prime;

void init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
% R$ S4 o8 G9 z            for(int j = i*i;j<= 30000;j+= i) {
- c+ B/ m& M$ h$ Z; l4 A. v                vis[j] = true;
; b: w4 [, ~$ d9 X1 g            }
1 A& e4 z7 _$ h- h3 B: O9 L        }
    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
1 h+ x. M# s9 M5 o1 Y- D    }
7 ^7 s0 q$ g. c/ m- j* H    return ;
& g; n9 K' }4 x' j  P. a/ h}
, O( @/ ^7 ]1 ]4 P
int cal(int x) {
    int num[123];
    mem(num,0);

    int k = prime.size(),cnt = 0;
% M( ^# V+ ]4 J6 Y* x0 c' A    for(int i = 0;i< k;i++) { // 分解素因子
) c* C  x! _  b4 Q% {( ~        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
            }
        }
    }
    int ans = 1;
2 X% ]. d+ y5 z- e4 F2 o    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
    return ans;
: C8 o  ]3 ?$ _% y. _- d}

, g3 ]$ Z* W$ r3 kint main() {
    init();
; s  z& g; K! U% Q) h    for(int i = 99;i<= 1000000;i++) {
3 I+ L' }0 N' j        if(cal(i) == 100) {
/ s6 ?+ R, Q4 O- i- E            cout<<i<<endl;
            break;
4 b4 D5 U7 Y8 x, q; h        }
    }
0 @- i, `2 y4 F
0 Z) q2 p! `. r    return 0;
}
+ ~- C; C% S, H0 S7 v---------------------
作者：nka_kun
3 g  M2 ~& ], s3 e来源：CSDN
! Z! l0 f" o" l" g

+ F& j0 J7 c$ F& Y" Z" ?! M