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

杨利霞

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

1 E( `( o! C1 F' G3 @; i' F
题意:  寻找有100个约数的最小数
& R) q, W4 r; u' p思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
/ E* l9 ^9 N3 o2 Q, D- C
% N7 H3 Y2 G& s3 x8 J" |, G结果:45360
$ L3 P* B0 S, c( V9 h  n- G
代码:
1 U  J4 p0 f% d+ |
#include<bits/stdc++.h>
0 i+ M8 y8 z  F+ Y#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
: G6 R0 N$ T/ H9 atypedef long long ll;
const int inf = 0x3f3f3f3f;
+ d4 g& ]- R8 g2 r7 dconst int maxn = 3e5+55555;
0 Q, b+ t0 C0 M1 y7 t# vconst ll mod = 998244353;
7 d% y, b, l' [9 g& \$ }const double eps = 1e-7;
" d7 F( I8 X/ b4 ?" r+ G
$ w0 W* _! C; q" Nbool vis[123456];
vector<int>prime;

( x* H. R9 t2 o. rvoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
            }
- f4 e+ W5 C, x% v1 S! t        }
/ f( P  \& j, t( w" p1 x: b    }
5 Y( w, K. [( d3 U    for(int i = 2;i<= 2019;i++) {
! j& n1 c) ?7 b) _        if(!vis) prime.push_back(i);
    }
2 g* c8 V' l$ R( K5 x, T, _    return ;
: b4 O. y8 S% ?" P2 S& C: G}

int cal(int x) {
+ A6 f8 Q; }% B# J( {0 o/ `6 {    int num[123];
1 m" Q$ {7 d% V1 i    mem(num,0);

    int k = prime.size(),cnt = 0;
7 ?( s2 ~' e0 E; c    for(int i = 0;i< k;i++) { // 分解素因子
  Y/ b/ k. ]0 h5 n9 k; X        if(x%prime == 0) {
; i  f8 S8 m, t            cnt++;
4 A2 I! P/ l. S2 _% |* m8 ~            while(x%prime == 0) {
0 w$ O( w  ]4 a) S' a. t                x/= prime;
1 B8 Q4 O+ c: f4 u9 ~6 B, e                num[cnt]++;
6 T1 j$ V, s) m* K1 l6 N# d+ b/ L            }
3 B) b, t, V9 @& B9 U        }
' V, }8 X0 M% Q3 o, e" x3 X  p    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
$ I8 p; M0 _: `* v: {    }
! w. ~7 V# M- m7 t+ S% F! _    return ans;
) Q* I* o2 u: o4 H# M}

+ W4 h% s( e5 X6 I" Oint main() {
    init();
9 @; F) M( |4 Q    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
7 r1 ~2 y4 }" W            break;
: P3 O3 |" E1 E3 W) S3 V" q        }
    }

$ Z9 \2 I& d! ?8 t7 n2 v    return 0;
5 B. W5 L" S. V' D+ j}
- S# J% ^- ], g: ?4 ]---------------------
; o3 x3 B( [9 {/ B" ~7 Y2 h作者：nka_kun
来源：CSDN

; Z5 P9 A9 `9 F: F  Z: g; p7 ?

1 M3 _% v* c7 y7 @/ b