查看: 2203|回复: 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) {
' p+ |" a6 g. C          for(int j = i*i;j<= 30000;j+= i) {
6 _) d+ h$ p& ]             vis[j] = true;
$ {% `% C7 f- A- W% r$ N2 ^( K          }
. m* z5 G" U4 Z2 c       }
9 J3 U+ L2 n% [  |+ P5 k }( }- T6 P; f, G) r' o. C0 B' r
for(int i = 2;i<= 2019;i++) {
+ d' ?" S5 I/ A& ^       if(!vis) prime.push_back(i);/ i. I& @0 K& \# c
}6 W* }4 y2 u2 o! E4 H
return ;. v0 X1 n, ]" ^2 e8 ~& _
}6 {8 \  V9 y9 t& K
$ B' E) n1 b3 P4 ]
int cal(int x) { " z1 Q. m7 M( T! t, v3 t+ b
int num[123];! X: x! \& g8 i- D* u+ ]/ ^5 v
mem(num,0);: w5 Q9 l* Z: f; m6 c
4 h! {/ E. K" I+ S* ]) p8 F
int k = prime.size(),cnt = 0;& `$ b; \6 S0 ~' \" \
for(int i = 0;i< k;i++) { // 分解素因子
0 W, @/ O- S' _# x       if(x%prime == 0) {, i0 v5 v$ o$ c# R" ~  l- X5 U
         cnt++;3 [2 b2 Z+ c4 b4 I: W+ Y% M" Q; m; R
         while(x%prime == 0) {
7 n# S) n7 G/ g/ U: r0 M' U$ P6 Y# k             x/= prime;
, P) k% ?0 |: B& V, v) {$ g0 j4 q             num[cnt]++;
7 O- w* N: m) F8 F- h! O2 t( S  C" a          }( x$ k  y- ]% {. [, \
      }8 A) R1 l. e& u7 Q# i7 z
}
5 G% g! W" G& b" g" P0 Q int ans = 1;9 G, F5 j% j. h1 {3 e+ w
for(int i = 1;i<= cnt;i++) { //计算因子总数7 Z$ d" O) m+ l4 Y% a
      ans*= (num+1);
( F# d# |- r! s" a }
$ g; E1 u+ w+ @ return ans;
6 ]: l9 w0 }- M# T4 _! e}
& r8 g4 `6 M3 l8 s# W
4 Q; L2 _0 x" t: [: u/ Uint main() {
6 P8 P$ B. N! Q$ }7 {8 v init();% B1 g0 U% j* Y" y6 S
for(int i = 99;i<= 1000000;i++) {0 l1 F4 t0 [  r$ U; ^5 @8 S4 g
      if(cal(i) == 100) {
# W, [# x% D6 z, y* }$ ]' d) l          cout<<i<<endl;6 d. B+ P3 g' f# W! q
         break;# t' h$ K, r( L+ ~+ f
      }
, d) t1 n3 Z" S, v) c, W }
, u% J6 r$ Y# w3 x# E4 i( G
* t# D" ~  H& [* Z4 o5 I+ v% | return 0;
, G/ S$ z0 b; R7 b6 r! f7 G}
% O5 o4 I; W8 U---------------------
  @# `) g' f, q9 k  `1 J作者：nka_kun
2 ]1 d# S  f6 @, H. K- g. x9 @来源：CSDN
6 J! x3 y2 N) e- d  F1 s# I( X3 g  s

) r" N2 G0 }3 f/ R+ H. o! @, ]! M1 e( |