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

杨利霞

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

题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360
; }& p) H/ @0 k5 {$ J. I
* B. c) q0 v; M代码:
. o, G" N# V8 n1 b" k  `5 W+ }
#include<bits/stdc++.h>
  \8 N) I) u4 Z* P. a#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
0 a! a* T, ~( z1 Y/ dtypedef long long ll;
' n; i" I8 t6 S# q& _, Bconst int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
6 Y& F3 i" d$ [' Gconst ll mod = 998244353;
- J% j+ W3 ~; }( o9 f) ?) ^0 [const double eps = 1e-7;

0 I# _$ U4 P; e5 {bool vis[123456];
vector<int>prime;
8 M5 a% ]9 }, F9 f/ j; w! W+ h- j
+ q# q8 [0 C2 C* hvoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
            for(int j = i*i;j<= 30000;j+= i) {
0 E1 t7 Y/ t2 S% e                vis[j] = true;
( x: h: W  A+ k; T: M; G            }
/ ], J+ [1 K+ p# d1 q( t2 ?* s1 {; a/ S        }
0 @, Y$ q% y' H6 Q/ R8 j) m' w    }
& Q1 f0 v+ z+ U, {% _    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
( a7 L/ n" }7 V2 T8 Q    }
    return ;
( [; K" k$ J5 a; h% h}

int cal(int x) {
    int num[123];
6 D8 @5 ^. ~7 ~7 y  |7 R# A/ g    mem(num,0);
) v# o7 q# C5 _6 e, F: |
$ z2 n" n/ k5 a. g* k2 B    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
+ Y, I$ _. l" j        if(x%prime == 0) {
            cnt++;
            while(x%prime == 0) {
                x/= prime;
( w! T% B5 [; |                num[cnt]++;
            }
6 ~2 n; m9 F* ]        }
8 D( L( Y$ H, P9 M# R  a    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
- A8 Z! l; R' P: ]2 w8 O! |1 k    return ans;
% T$ H3 c0 o$ }% i8 X}
  m. D% r7 p( b, B7 }8 X
+ a/ \- o6 s6 r9 f3 ]int main() {
2 t( h1 Y/ q/ L% O* L, S! S0 L    init();
    for(int i = 99;i<= 1000000;i++) {
) ~7 {* b1 |2 G        if(cal(i) == 100) {
5 }6 _# t5 E6 d0 X, M# G6 K            cout<<i<<endl;
) n/ S6 f- C0 n2 L            break;
        }
    }
% K& _; J0 K: B% X3 m8 w/ y6 m0 y
0 ^; @, b# f* @- ?6 Z) H    return 0;
+ X/ o5 I8 z# C# I" S2 d3 s4 B* _}
---------------------
作者：nka_kun
来源：CSDN

$ J+ j, ?/ P! o