查看: 2144|回复: 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) {
, O' u+ t6 G8 s5 W. N          for(int j = i*i;j<= 30000;j+= i) {
3 c" z9 m6 ^& A2 n# Q, B$ d) E. D! |             vis[j] = true;
' r! Z  B5 |' X          }
1 J- Q7 p0 v2 g       }. ?- ]0 Q3 w' d0 x) J
}8 ~3 E; U7 z  `  k7 X& R
for(int i = 2;i<= 2019;i++) {/ G/ T7 V, b. S) I- b
      if(!vis) prime.push_back(i);
' I" ~; g; h/ G- D }
1 [# a+ b0 u5 S! s return ;+ i" d2 J' H5 t. ~. ]! W
}7 \& F' o$ ?% l
! R" b% I# I* I' U" j3 ^
int cal(int x) { & i' b4 \4 y, L
int num[123];, [/ U) r- G$ ]" z, T' \
mem(num,0);
/ ^2 l; q; I8 V' o
) Q: ~3 }% J$ B6 ?* Y int k = prime.size(),cnt = 0;" ?5 v% ?$ |9 O/ U0 h
for(int i = 0;i< k;i++) { // 分解素因子4 C6 F- V" ~0 g% [* w* B* T* p
      if(x%prime == 0) {2 }: j3 D  ?9 Z5 i1 P2 g
         cnt++;
: X$ P' @8 \; I( z- _          while(x%prime == 0) {2 u, |7 X, F; h  ~' G2 b
            x/= prime;
1 m7 n, O: B2 t* r6 b, E             num[cnt]++;
* v) Y0 k/ n* d          }
0 w( O8 p7 i1 h( f5 I9 F       }
# Z4 Y1 v2 c" u$ t }1 N& B1 u$ |. R0 W$ t, A% n
int ans = 1;! O( c# ]5 U7 x$ z. M, o: J
for(int i = 1;i<= cnt;i++) { //计算因子总数% g8 s8 n/ J, X! M) |
      ans*= (num+1);0 X1 N2 t0 X* ?1 K' N/ c
}2 z$ f$ @/ Q, G  i% m9 X1 p
return ans;7 s9 w$ v4 V- a' Z2 p! S
}( ^. Z! i0 E9 a9 D

/ ]/ B! K  v9 Z. r; tint main() {
* d+ `$ u1 Q, Y% S init();
7 s7 F+ e5 M3 I2 H for(int i = 99;i<= 1000000;i++) {
. \5 B) Q: p) p; `       if(cal(i) == 100) {
! n0 c0 y7 U. ?          cout<<i<<endl;! {2 H2 @) `- Q( z
         break;
! i5 t# j+ [0 a% l' ?+ q       }
2 H: _- u0 S3 k8 M }1 b; p+ O( V: \% j2 o3 @

, N; A9 h& z( U/ D6 `) t3 j% E' P return 0;
: [" W/ ]' R" Z: U% S7 g2 Z}
- I7 C0 Y* j" T' x( S8 [& R' N% M---------------------
7 ^, R4 `' j3 |2 k: m0 D  d作者：nka_kun
) V, g2 Y! _7 D; {( B  A& p8 T来源：CSDN
+ @0 T+ R) I& h
" ]# c6 Z) |: ~- |6 ^8 H5 B: b% w0 ~$ b
2 Q! n, Y, |/ Z+ C: u; k6 v