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

杨利霞

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

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

9 V, u' {1 C+ [& I' x* e3 f3 ^, i# z结果:45360
1 H5 \6 S# u8 ~! E; \3 z
代码:
6 p( C% F9 G# G5 _" Z5 _, C# H% _" d
( `, H6 B- s( {/ x- F#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
9 x! V. e, \% uusing namespace std;
* ^+ T! H) s5 ?2 _$ btypedef long long ll;
const int inf = 0x3f3f3f3f;
5 x, ?; D+ Q, o+ i9 w6 L1 k- T0 |const int maxn = 3e5+55555;
3 I9 D% n( C% l) q* A9 Z8 H2 Tconst ll mod = 998244353;
8 c0 }$ b/ ?, Z! [const double eps = 1e-7;

bool vis[123456];
& D% g: t' K' s3 Z: l  g6 ^: `vector<int>prime;
) r) e: F8 o# V5 ~, n& P
$ ^9 E% u9 C/ o" f# F- e7 rvoid init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
) A0 i; [6 k! U; j$ i4 D' Z+ B            for(int j = i*i;j<= 30000;j+= i) {
                vis[j] = true;
0 s( P6 l* Q2 g% x7 ^) F0 e7 b            }
8 b7 O6 o: Z9 k- ^, c% G* t        }
9 d& @9 h3 }: D    }
    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
    }
# S* F3 Y( }  {/ \/ j4 ^& X    return ;
8 J+ x# A5 X" Q& j, M! r: g8 m1 U" M}
4 n8 I  d% _1 p1 h
6 i2 H4 I; v9 E/ }2 {6 \int cal(int x) {
    int num[123];
( u$ T4 {9 n! m( ?    mem(num,0);
8 Z# m! [4 F3 h. M" Q
    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
- n4 ?/ q3 c+ Z& e% D  x. N        if(x%prime == 0) {
            cnt++;
% D8 ?: r  I1 \: ]( q1 T2 i% |- p! P& }            while(x%prime == 0) {
                x/= prime;
8 D- O, C& a7 V$ F9 A% e                num[cnt]++;
9 z, L' N3 d# A8 x            }
* v. @3 P( J1 Y        }
    }
* |) |2 V5 a' t' y' y    int ans = 1;
! |/ x% `" i! x+ Q/ `3 ?    for(int i = 1;i<= cnt;i++) { //计算因子总数
        ans*= (num+1);
    }
    return ans;
}
9 G& `4 \! |+ P" h
int main() {
    init();
    for(int i = 99;i<= 1000000;i++) {
% w+ G, f  }& n9 H( B- l" u; v        if(cal(i) == 100) {
            cout<<i<<endl;
7 S; B# l% @5 p' [( n6 l            break;
. s) @* w7 j1 l7 ?! j5 O        }
    }
+ z( ]; F# ~# \, F5 `4 Z8 s
& n0 E! u0 H" ?% r- J6 t    return 0;
}
: j, [: N, S( N# W9 b+ @---------------------
# e3 _3 t! K/ j. O) q作者：nka_kun
来源：CSDN


) R7 H/ B* \! C9 _: `( r/ {  C