查看: 2167|回复: 0

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

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 15:53 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

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

结果:45360

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[123456];
vector<int>prime;

void init() { //素数筛
for(int i = 2;i<= 30000;i++) {
      if(!vis) {% A* A6 Y- U) g3 E/ z. a, ^' _$ I5 S
         for(int j = i*i;j<= 30000;j+= i) {
* I8 I7 T- d) v) N: S" I# _: ?             vis[j] = true;: r, }' M3 c2 ^8 g# y
         }$ @; c- H" {" t! b$ x# z
      }
) ~) [7 C! Z9 z  o0 i7 L  b }8 Y6 q1 ]  B% V$ E
for(int i = 2;i<= 2019;i++) {$ X! |6 {* P( ?. G5 c% L5 |
      if(!vis) prime.push_back(i);6 t( ^5 ^  F' _8 o, u, I  f
}7 [3 H7 Z5 S" w' {4 o- K, w
return ;# B+ h$ x) _9 N. N6 F5 A
}$ `8 Q: O0 i: Y- e- v0 D1 u
6 c+ A4 l7 ?% y. H3 y
int cal(int x) { $ v7 Z) w; W8 @+ K( z+ F8 Y4 H
int num[123];$ J( _0 K; x0 Q; U" l$ O; W3 `
mem(num,0);. |  f! W% m2 Q
' g4 t; I6 {# u( p$ U. R
int k = prime.size(),cnt = 0;
' w. H  Z" S+ z! ^2 s# u7 D) v' A for(int i = 0;i< k;i++) { // 分解素因子
3 B8 F8 a4 J; B$ h( A. `! m+ z       if(x%prime == 0) {7 P. L3 H: T2 b) C& d
         cnt++;3 `" k$ s* S. ^- k# `0 K( q
         while(x%prime == 0) {7 F  U" b& ?! e: U) B
            x/= prime;
0 I  w& i3 M$ U! G+ W: J  O' c             num[cnt]++;8 A& G. J" N+ @* [; J; k$ W
         }
1 ^& k3 x% l  P. d# i' q       }
- @+ U0 n) f- e9 r% h/ y7 e }+ m( |" ~  U  |/ u* o& l6 S+ l
int ans = 1;0 Y% }) O1 P' Q. x9 ~% p1 |5 O3 O  p
for(int i = 1;i<= cnt;i++) { //计算因子总数" Y% ]9 t2 j/ `+ E
      ans*= (num+1);
' `) G% W; Y- W$ M& ] }/ k' P2 D; n' z) t5 g
return ans;- H1 G5 S" i- t, C& ^8 Z
}3 @3 c- e/ U" d3 U2 ^
) I* o2 y0 e5 I) k
int main() {
3 m$ a9 Q% O3 Z( H. F init();
& U4 J) O8 H0 ?  A7 _ for(int i = 99;i<= 1000000;i++) {
( a6 h0 V7 ~( F" V9 ]  [/ W! j0 Z" n       if(cal(i) == 100) {+ h8 \* Z9 o: J( C0 K2 Q) v
         cout<<i<<endl;' m1 O2 A6 H3 ?1 Z
         break;. T# r  S0 h! ]5 ^1 X2 t- u
      }
+ z$ {( e% j" I' _8 \8 S }3 B7 i( {4 U1 a
' d8 V+ N1 D# J+ O8 ?" [' r
return 0;
5 Z7 Z$ `& T0 S6 K* L5 q  i' t( L}" d% `- S" Z! A9 B0 {7 j1 W
--------------------- 4 o$ r% r5 z0 f6 m9 [
作者：nka_kun $ M2 v3 g& z6 K1 p2 W) g4 B9 u
来源：CSDN
$ Q' X8 k0 f. w% l
1 g8 S  B+ x. F- f
' \8 o0 r- o+ U# R. f! s. g
; l1 q. A* @) W