数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第四题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:53
标题:
2019第十届蓝桥杯B组决赛题解第四题
2019第十届蓝桥杯B组决赛题解第四题
# u0 k6 `1 O! M M, v0 L5 Z
' z8 f& j1 m2 b* B
题意: 寻找有100个约数的最小数
! g2 e: K- Z+ u% R
思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
: p0 y n! a; k( n, U
$ V% X$ h: z. n) p- }- ~# X) e
结果:45360
; u* ~1 P6 q. @' a
7 [5 n9 x/ G G7 N5 o
代码:
2 I8 u/ H% R. S- w
) F+ W7 y/ A4 f/ u
#include<bits/stdc++.h>
& @/ }3 n+ D& Q( M4 m' G
#define mem(a,b) memset(a,b,sizeof(a))
' d- ]) C3 I9 K* M
using namespace std;
) ^, L2 S' Y, v; b) t
typedef long long ll;
+ [8 ~2 t& p0 n( k$ E
const int inf = 0x3f3f3f3f;
; r, J: S8 h. q' M" [4 c
const int maxn = 3e5+55555;
% j% o$ E% G G) C ]. S4 {+ n5 y. N
const ll mod = 998244353;
/ P# L% M' \# _5 W; u: |$ Q, E
const double eps = 1e-7;
- H) m" c1 x) Y6 ]9 u" ~3 b q' q' u
: D% O W7 s' l; _: {% H1 a% ]
bool vis[123456];
, y2 T3 j: \2 W3 t& Y) U
vector<int>prime;
1 C& o2 X+ B' X3 T1 @, b3 T* |
" c, l, q# s0 U1 |7 c
void init() { //素数筛
7 K: c- d9 @0 g* H
for(int i = 2;i<= 30000;i++) {
6 i6 z2 r) ]2 c/ C* m; G
if(!vis
) {
) L J+ {, Y# C- j0 Q
for(int j = i*i;j<= 30000;j+= i) {
; e- P( p6 Q) s
vis[j] = true;
. C# c X$ n) S7 J; ?, c
}
4 |/ i! f$ D8 ?4 L! c
}
) E1 [+ d! ?2 K
}
% U& R, B; u- s$ \+ T* }
for(int i = 2;i<= 2019;i++) {
9 _& h9 o% x" i* l
if(!vis
) prime.push_back(i);
' }% z& Q6 Y3 |$ w% K a% Y) p
}
1 H9 ~& {4 d, a9 u
return ;
5 f4 H0 H, F1 W. t+ N+ L6 @
}
1 g4 T: ]* A) e7 V
+ h9 x" a) |% x2 |. x) \3 J
int cal(int x) {
; w( U* ^$ ~4 b6 S
int num[123];
5 _9 }# ]6 P4 b5 N
mem(num,0);
- ?7 `; r7 Q5 A# e! {* N0 R
9 y: I2 L7 e$ w7 G
int k = prime.size(),cnt = 0;
( x% |' E0 s. o1 [/ p
for(int i = 0;i< k;i++) { // 分解素因子
- r4 K. w, M- ?% n0 e
if(x%prime
== 0) {
9 M& v, P% E+ F0 E* c( r
cnt++;
4 X; W( X; q* l
while(x%prime
== 0) {
7 P8 W! c0 q5 X, t3 |7 Z
x/= prime
;
( Z4 r+ j9 Y" m7 Q# `
num[cnt]++;
! e( K+ l1 r* ]- T% r3 u1 O7 m
}
. g0 s( Y7 O( s+ S- W
}
! g, g6 x1 A: J( {( I, g# z
}
8 b' p) A) Z& T/ x; G
int ans = 1;
2 _ l$ r- c/ k$ q& }) S1 L; D
for(int i = 1;i<= cnt;i++) { //计算因子总数
8 m" Z% r% ]6 ]# g' K% ^) L
ans*= (num
+1);
5 \* z8 o% h6 a
}
' |& O a, v; y* T
return ans;
, @4 J- \4 L& C3 l7 z
}
- w) p: H1 C! }8 h0 q) X
! [5 U7 ^: \0 l$ u# z" t
int main() {
" S0 g) |! O/ n& I7 _0 M
init();
# D2 B: N. c& v3 G2 a' x/ Z, ]$ q
for(int i = 99;i<= 1000000;i++) {
4 h# m# a) J% \5 [8 W
if(cal(i) == 100) {
* R0 ^" z |) Q% t; q7 e
cout<<i<<endl;
& B" y8 S4 a8 C9 k3 A$ Y7 b ^
break;
2 C5 E/ p" Q- X+ y
}
: ^ [$ x9 j- w, P3 l: f
}
# I R+ n! P7 s ^! I
7 H, [2 R `+ I, k$ r
return 0;
' Q/ y/ m; l# F8 w5 t
}
; G; R* _3 x: |5 a6 W
---------------------
$ X! @ ]5 K! D+ X
作者：nka_kun
# W; i; O3 x4 S6 K7 Q( N6 m' h- [
来源：CSDN
5 n8 h g" d0 v& F" ^4 }/ d& \' l
# i6 d/ d9 _% M9 |
, C3 X! ?! F1 c+ ?
1 F0 M" G8 [3 ]$ }
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5