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

杨利霞

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

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

' f! z( N& k  {# j" ^+ X+ B+ H" V$ j结果:45360

代码:

#include<bits/stdc++.h>
$ I& K& k  p* }#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
( s% ^8 m9 |0 m) H; Atypedef long long ll;
const int inf = 0x3f3f3f3f;
4 R( _1 E! _$ L( qconst int maxn = 3e5+55555;
6 E) J2 M- ]6 Fconst ll mod = 998244353;
3 m0 B2 x% E: P- I& Wconst double eps = 1e-7;

bool vis[123456];
vector<int>prime;
1 s' T2 ]" A* o2 b( t/ h
void init() { //素数筛
    for(int i = 2;i<= 30000;i++) {
        if(!vis) {
8 W0 ~- x; O/ R  Q' u            for(int j = i*i;j<= 30000;j+= i) {
5 Q( e. a7 p2 h$ m! T                vis[j] = true;
            }
        }
    }
* b: [' d- L  \8 H- M  T    for(int i = 2;i<= 2019;i++) {
        if(!vis) prime.push_back(i);
9 V1 ^' ^( Q) ^, }% q# I    }
' S- @9 G& E4 u3 c2 x8 c    return ;
}

* N# I6 u& Q- U; B2 cint cal(int x) {
    int num[123];
$ E9 v" S: a. F; j0 s8 o    mem(num,0);

    int k = prime.size(),cnt = 0;
    for(int i = 0;i< k;i++) { // 分解素因子
: a; ~% S2 G7 u. q! Y        if(x%prime == 0) {
/ P2 ?% y; r0 U3 b4 ~2 u! K            cnt++;
3 K5 L- b0 M$ s: E$ k6 x3 D$ t+ R            while(x%prime == 0) {
                x/= prime;
                num[cnt]++;
            }
0 D4 E# o# T: m3 X0 c0 D        }
    }
    int ans = 1;
    for(int i = 1;i<= cnt;i++) { //计算因子总数
. Q% n4 A5 J8 g& d5 p2 ?, w        ans*= (num+1);
    }
    return ans;
9 L+ z( o8 o4 [. {1 @1 ~# k5 O}

, Y9 P* M' o9 q" ?4 iint main() {
    init();
    for(int i = 99;i<= 1000000;i++) {
        if(cal(i) == 100) {
            cout<<i<<endl;
: p5 ~* q- \- a5 Y6 a' y            break;
6 L% B5 T' V* g; c) i2 n        }
0 i" @1 f4 `1 g& O: J    }

/ F+ R- U2 x& D; J( f    return 0;
}
---------------------
$ `& \. O* c1 f9 E' t  C- q作者：nka_kun
来源：CSDN