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

杨利霞

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

& `2 R1 q( o$ K4 F8 B0 o" U% @
% t+ f  A! \4 \% }3 b, S题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
& {! [5 n- G, x. O6 s; [! l: @( Y
结果:45360
; K* }6 F$ b5 i
代码:

#include<bits/stdc++.h>
) }8 i0 r/ d3 N# u#define mem(a,b) memset(a,b,sizeof(a))
- _  D1 D  U0 [  U. M% I7 Pusing namespace std;
) s7 H- G& y3 z# [typedef long long ll;
& R% Z3 T/ }4 d/ R6 E0 X; i2 Qconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
. e4 G& g* N2 P$ o" g* V- ~const double eps = 1e-7;
% B3 J7 h9 g; c& P. b3 ^0 G4 }
. v- t6 ~, k# o& K/ ^+ n+ c' s; cbool vis[123456];
vector<int>prime;
* h( g3 X' `- H: N* h& g) K* M
& v( f2 {2 @0 Z  W" p5 Gvoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
5 L$ N$ K' B8 N' M9 p/ |        if(!vis) {
% x# q% X3 z: i8 h( _5 j: d, J            for(int j = i*i;j<= 30000;j+= i) {
6 G" N6 F" v/ m3 D2 J2 y                vis[j] = true;
            }
, X$ C9 N* J- j0 i( V. q- ?        }
7 Q$ _$ b# L0 C8 m& K# j% Q    }
    for(int i = 2;i<= 2019;i++) {
3 ?+ _) F: u* H- t. \  Q- }; j) }& d        if(!vis) prime.push_back(i);
    }
2 s$ w8 R; \' t; ?9 M9 P    return ;
}

int cal(int x) {
  E+ M0 i, X  q8 @# D* @) A    int num[123];
    mem(num,0);

! g0 x1 s. Q' ?, r5 H( N2 @6 {    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
        if(x%prime == 0) {
, D. ]1 ?0 Y; R5 q  k3 F            cnt++;
            while(x%prime == 0) {
                x/= prime;
* b$ |  Z6 n4 g! T. I* ~4 B                num[cnt]++;
            }
' ?" p: v" R% Z' t3 u) \        }
1 `( L7 u) H8 b: N    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
* [: \  P% P& y4 z    return ans;
% d, q) R6 c6 y' u4 q}
, X% Q/ ?3 g# P$ H8 D, ^$ X* k
int main() {
* ]) c( s- r$ S! s    init();
1 U' z6 F  B8 w5 ?$ j    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
! z; C: r8 ~/ v* W) A$ X            break;
        }
    }

1 `4 O0 q' f2 k$ S. o( z    return 0;
}
---------------------
, Z+ h, r( C) @! [5 a3 P5 p. u作者：nka_kun
来源：CSDN
6 G, x* L" J& Q' w* A! F: @
5 M9 F* O1 y' I& E0 k7 |