- 在线时间
- 1630 小时
- 最后登录
- 2024-1-29
- 注册时间
- 2017-5-16
- 听众数
- 82
- 收听数
- 1
- 能力
- 120 分
- 体力
- 564697 点
- 威望
- 12 点
- 阅读权限
- 255
- 积分
- 174632
- 相册
- 1
- 日志
- 0
- 记录
- 0
- 帖子
- 5313
- 主题
- 5273
- 精华
- 3
- 分享
- 0
- 好友
- 163
TA的每日心情 | 开心 2021-8-11 17:59 |
|---|
签到天数: 17 天 [LV.4]偶尔看看III 网络挑战赛参赛者 网络挑战赛参赛者 - 自我介绍
- 本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。
 群组: 2018美赛大象算法课程 群组: 2018美赛护航培训课程 群组: 2019年 数学中国站长建 群组: 2019年数据分析师课程 群组: 2018年大象老师国赛优 |
|
2019第十届蓝桥杯B组决赛题解第四题 8 {% H. p$ M) @, s
2 I" A7 W/ m: `题意: 寻找有100个约数的最小数
5 Z7 G1 Z5 _9 [+ m) g思路: 本质上就是用了素因子分解,假设分解出来的素因子有4种,分别有x1个,x2个,x3个,x4个,第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)7 G: a7 l) Q/ \# r% u4 G
" u5 @) N3 f5 L, R. Q' ?
结果:453600 B2 T+ r$ W: A) |: W9 p
* s% m" }( X ^' f; i代码:
5 [: [ h6 G; T1 s0 V9 \9 x2 Q+ j$ P! W: Z) z" f. M
#include<bits/stdc++.h>
+ ^3 K7 k1 { |& ?' a K#define mem(a,b) memset(a,b,sizeof(a)); l i6 D3 H3 t, E
using namespace std;) \6 v* g$ [8 Z) P+ Z7 i, x
typedef long long ll;
! O. N. @& U% S& B4 W2 \6 [0 Uconst int inf = 0x3f3f3f3f;
) H$ |3 g% S( t" j' N9 b7 o# t4 X5 x% uconst int maxn = 3e5+55555;0 P5 Y# p; x4 t# j/ d+ B; z1 p/ t: f# n
const ll mod = 998244353;; |' J1 k W4 K, R
const double eps = 1e-7;
+ ?; j# E8 X& ~& G) G* W; h. O% C# \5 b1 V9 D
bool vis[123456];
6 G9 L5 y" M6 vvector<int>prime;5 i( K% G: ~$ w, h8 o
4 A7 Q; d; g8 uvoid init() { //素数筛
# ^ J, w' N4 U9 C for(int i = 2;i<= 30000;i++) {
" {7 O( Y" s4 i if(!vis) {8 u* l+ E: `& V( q7 T* |: F7 N6 i& l
for(int j = i*i;j<= 30000;j+= i) {1 h5 d" l; _/ Q7 Z. J: y1 `
vis[j] = true;
. U3 z; h V8 U$ G+ W. L4 ?, t }# K' G8 ]4 d& {8 J2 F) T% T# Y9 u
}/ I, r# V( ^" b: r6 p) w! E
}
L/ ]! ~, x/ k" ]7 `& ~0 t for(int i = 2;i<= 2019;i++) {
/ S0 \8 |& d( c" n; h if(!vis) prime.push_back(i);' N0 T) ?& t0 o, |/ S% R
}
% s: n o5 A1 x7 y8 d' r return ;9 C0 B( Z G5 y
}
0 n: p; g9 n1 j+ [. d# a
& v& t. S5 Z9 H J( g% Qint cal(int x) { 8 X. D' \& R, T+ A- F; E3 l
int num[123];; A' D& U2 s9 r* H x
mem(num,0);
4 i. A; I* P& c* [/ V9 J4 B; X' q6 y, P; G3 Y5 `
int k = prime.size(),cnt = 0;
* f. {: c/ k: a0 u( r! B for(int i = 0;i< k;i++) { // 分解素因子. A. P) f+ n$ n, i) v
if(x%prime == 0) { X7 X6 E% C' `3 `# N; n. w: Z3 g
cnt++;
; D; M V) q( L8 ]- {0 M while(x%prime == 0) {$ S Q( s& y! u1 e
x/= prime;
" z/ {% q; c W. y$ e num[cnt]++;5 `2 K9 j" k" |2 Z$ M5 W8 D
}
4 t4 q1 r' k5 x: R; ^4 H9 g" L }" ^$ B$ n4 P/ C- K) F
}
1 d+ w9 S7 l% t8 x int ans = 1;' [ e+ N( h. \! G6 l
for(int i = 1;i<= cnt;i++) { //计算因子总数3 Y9 l5 `- B" N7 I; |2 Q! X5 u
ans*= (num+1);
8 F5 G" g1 [* J3 X. V/ a0 X }
! @! }6 N- p: p; o0 v+ S& X7 R$ A return ans;
6 _9 R1 n% z, t- \4 |}
! e) s: x; G0 T G& x* Y+ H1 \/ o( W, o
int main() {
% y6 O) I1 @; `# Y" j; h init();; W+ e' K9 A, e
for(int i = 99;i<= 1000000;i++) {
' `( p$ ^& n9 } if(cal(i) == 100) {% M5 B& z' j$ c
cout<<i<<endl;, p3 l8 B# K) ?( H8 ]5 `
break;
' g; `6 _, v; ^% F- A! N8 b }) R5 j2 M8 b6 V6 x) a$ b
}$ B* Q0 ?( W6 f5 h1 ^; [% j
1 P9 C/ ?+ V7 Y0 b {) c return 0;
9 v' D1 e& M$ m+ c, y$ `9 ]) p0 A}9 l9 _" w+ \1 [: m1 T
--------------------- ! s/ b |( z4 ]7 {6 d8 q
作者:nka_kun
- k. f, {" F( W* S5 a. T来源:CSDN 4 ?7 }. F) d" V5 {- V
% d; X9 `) Z9 Y& E# P {6 P
2 D) s1 N \* J' t9 |! b4 n
9 |: n+ N1 a! {' @/ ]& Z% I |
zan
|