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

杨利霞

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

$ z7 l; n3 b7 |7 ^题意:  寻找有100个约数的最小数
5 D7 m# l* t+ {4 O思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

. J+ ]) |1 [" R1 q/ Z: N0 e. [代码:
3 }; t+ k6 A/ j3 x
' Y% ~( m; a4 Q#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
, |3 [: Q6 f2 \; _: i+ Ptypedef long long ll;
7 z. |3 T3 a5 \  Cconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
8 R/ d( r  t: _. ?3 N# V8 S' Cconst double eps = 1e-7;

bool vis[123456];
vector<int>prime;
% M* v# A: r4 V+ u% @3 @- h; Z
void init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
2 @( k$ L$ S/ v: v' W4 A        if(!vis) {
6 y+ B8 p2 V3 n% h. s            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
9 o2 N8 ~/ Z: Z& K        }
3 t( g" r, K9 `3 |& h, ]  K8 u    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
# ^: d" c" T' ~/ ~3 N    }
    return ;
. E8 Z- E! `' ~" ?1 Y5 b5 {}

7 f" a3 [% m5 @' ^3 u$ C- i, Kint cal(int x) {
    int num[123];
    mem(num,0);

    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
" P; b7 x0 O6 X                x/= prime;
                num[cnt]++;
            }
        }
8 E: M: A; a, F6 v    }
    int ans = 1;
; U5 O  a3 q# |/ I' E    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
    return ans;
" N6 F& D$ P' s}

int main() {
- ?5 W* u* W/ r+ p- M    init();
    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
0 ~7 X# H+ X0 Q) v3 h/ M$ g            cout<<i<<endl;
! p5 d1 a1 |$ Q& C3 D            break;
; n2 Q/ B8 Q* P        }
5 q1 k. _) E! S' E    }

    return 0;
* V1 c$ v0 {  I7 O5 x}
) Z  }4 j' T5 @& r$ A1 ^3 k8 E---------------------
. ~) v! a: U0 [/ L作者：nka_kun
来源：CSDN
& F& e) P, z# u' l; q: f- s1 E

& B! O( d' s$ {8 G4 H