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

杨利霞

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

) s6 E; v; Y" y  J0 O2 P! x
; Q) e% r0 D5 y1 `: E2 o* {题意:  寻找有100个约数的最小数
4 L+ V( g9 w. B7 F( l* s思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

! o+ F+ B5 h. B# p. M: g: E结果:45360
" d- s  K0 R' b9 g9 h( k0 r& }; ]
/ e" }/ O* A( ?代码:

#include<bits/stdc++.h>
; b1 i: a* w( p% t" \#define mem(a,b) memset(a,b,sizeof(a))
  X3 a# o. h0 @0 R# h7 d" Vusing namespace std;
typedef long long ll;
) Y1 e$ @& R( V  [& G1 V  l  yconst int inf = 0x3f3f3f3f;
4 u! o, h4 u& |( I) Pconst int maxn = 3e5+55555;
const ll mod = 998244353;
$ m3 Q$ S7 c( I5 Bconst double eps = 1e-7;
6 ~2 k: r4 v" t+ `, [) Y
- P4 j3 \: Q$ h& R* Gbool vis[123456];
vector<int>prime;

# N* H$ [1 Y: U" q, Q, D. @! Fvoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
7 P$ C% t. m1 Y4 N8 A7 I4 M                vis[j] = true;
4 X  h' ~9 D. o1 q8 r1 p/ S            }
3 u$ K7 b' q" c3 \+ B  i        }
    }
- B  M, y% e5 ^; @5 H2 c/ B    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
8 @2 y) G. t7 h/ A3 y8 Q    }
    return ;
}
1 Z8 I1 K: W: L
int cal(int x) {
    int num[123];
1 ?1 k. B% C  q    mem(num,0);
& A, C- A. q' o- r
4 S# p( E% w: i+ f. V    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
; f  s; I5 ~" v; \        if(x%prime == 0) {
* O3 ]$ ~; s  E' k* X            cnt++;
) x. ]& I( T4 {% {7 u            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
            }
        }
5 O/ L, t! P. y3 t2 f" O/ s    }
, k" B1 m9 k7 }6 `' I! o    int ans = 1;
$ S! @. Z& Q0 e- k6 H    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
    return ans;
$ m/ b, a( d5 T  k& }9 L4 H}

int main() {
( C& m7 p8 ?+ T+ i3 ]  N1 ]    init();
' `  H# P. T$ ]0 P' `    for(int i = 99;i<= 1000000;i++) {
: v2 s0 d2 _8 Y- K        if(cal(i) == 100) {
) O5 j7 |0 U6 B% m            cout<<i<<endl;
/ n# h4 R% f' G& ~( ~0 d9 j4 ]. L            break;
        }
2 E( ^& x( C" L' C; b9 \    }
  y$ s; d: x+ L9 j9 U$ ^" N
& _; R% e" U* a" u3 f) F: q    return 0;
}
---------------------
作者：nka_kun
来源：CSDN



3 G# b3 Q' p6 X