数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第四题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:53
标题:
2019第十届蓝桥杯B组决赛题解第四题
2019第十届蓝桥杯B组决赛题解第四题
6 G t [- G# p( u3 {) q9 J
# y# j) ?) ^6 y5 R+ _7 F% L& P5 b0 b8 \
题意: 寻找有100个约数的最小数
4 y8 m6 B4 v6 F- \& p
思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
+ G+ o) T2 `- V, }# m
8 a) J9 b; L9 c9 e( e) z( B
结果:45360
3 K2 Q: T8 V& x' P' {
5 C6 g+ O! a, K* p
代码:
1 n! N+ c+ a6 M
' @' |! w: {# W2 A% f' ~8 H2 E8 Z
#include<bits/stdc++.h>
1 U( |1 e# z. G* [
#define mem(a,b) memset(a,b,sizeof(a))
+ m5 G# n* ~: B$ c' k& Q, }2 k* I
using namespace std;
7 u4 {( \. p* I; a
typedef long long ll;
# q* L0 ^; D0 K
const int inf = 0x3f3f3f3f;
j+ h/ l, `' @$ E" p7 @( j' o/ J
const int maxn = 3e5+55555;
/ C2 g* Z8 k( M9 X
const ll mod = 998244353;
0 z0 d7 N% j: F% ]$ @ c
const double eps = 1e-7;
" ^" S+ q8 Q, G# A5 z+ J# q
' U! F; r H& ^1 N# N+ \1 G% M
bool vis[123456];
$ B) g. L. n) j$ y
vector<int>prime;
3 K6 Q! @( }6 q2 Q6 t/ }
& c" u) _7 e* W3 c) b8 p& h
void init() { //素数筛
& v$ I; G4 |" W# |' J. F+ b
for(int i = 2;i<= 30000;i++) {
1 W/ M! Q/ w3 D% v* Q
if(!vis
) {
- x4 d, h8 u: ?6 N7 x' T4 W u3 |
for(int j = i*i;j<= 30000;j+= i) {
! I- ~$ n$ r% f4 y2 Q+ {
vis[j] = true;
6 ~5 O: l. D8 h) l
}
' A! L' g9 Z; W$ I$ k5 q
}
' G0 f* _' ~; B
}
# ~$ \; ]5 E5 F( K
for(int i = 2;i<= 2019;i++) {
' w `& y$ n' N9 Y) A3 ^' k6 C
if(!vis
) prime.push_back(i);
+ h+ s5 ~7 z7 h/ T; U
}
1 U- y; }6 N; L& u
return ;
9 {3 ] E8 U H3 \# C; s2 G
}
b+ ~& e* f; Z& T6 ]
0 p% O* ~/ w. { O
int cal(int x) {
, ^, D4 N* x& A% x7 F- w% I" m+ b& U
int num[123];
+ {! i% k& _/ |. t0 q2 [4 D% \
mem(num,0);
. k1 u$ z# c& u; ]6 O
5 q p$ G# k/ f+ V* Y
int k = prime.size(),cnt = 0;
/ E9 W- M6 C8 D2 I4 _2 E# |
for(int i = 0;i< k;i++) { // 分解素因子
+ Q; g! W) k# P0 c I& [1 r& E( a
if(x%prime
== 0) {
' p" G& l% _- \! q- C! X4 \! i
cnt++;
/ v0 U9 ?$ \, a% I u
while(x%prime
== 0) {
3 G1 i# A4 S, X( ^$ g% p
x/= prime
;
, M' S0 y4 W& K
num[cnt]++;
1 t! b5 P6 m' C
}
3 j) F( _2 Z* ~8 F3 P
}
* B' D: l. K; n6 L* z+ y
}
; L- [, H8 ~6 b4 D- s: _
int ans = 1;
6 J: k6 t, C6 d2 n! ?% ?8 F
for(int i = 1;i<= cnt;i++) { //计算因子总数
2 A1 u+ ]) C% y) q# [& a& O
ans*= (num
+1);
1 f. E5 l& `4 |) j
}
5 V. v3 I: `, S. b: p
return ans;
; L7 b3 y. y2 ]/ [ V" m- E* X' d
}
: e0 ~% [# F. x
3 G! p5 Q% g( y" L- K: f
int main() {
+ j/ z( Y: d2 q" W. J( Q& Y7 A
init();
F" B$ H5 R; e# J) C
for(int i = 99;i<= 1000000;i++) {
9 U! K, l+ A# Y, Q6 N; P
if(cal(i) == 100) {
- E7 A, _7 q7 [: X; y5 k
cout<<i<<endl;
' M& T% c5 g, A: N- D
break;
9 C, k) L3 ~+ T" b
}
0 s" Y2 P0 N, @3 p/ V3 K1 D
}
; j0 g5 X. c! g5 h
9 D# z4 l; i* i N3 B- e7 K# d3 \
return 0;
. {+ e" b0 L9 t2 a0 Y1 s
}
' W9 p$ ~# y( T2 q1 x
---------------------
6 ?* r" J* m/ V2 m! k
作者：nka_kun
. ~# @ H" Y8 \. \0 f! q* ]
来源：CSDN
: n( A4 Q( u# @
& {, c9 S- q* W; `1 _
D/ J" D0 G# H6 j) F' f
0 ]% x0 z$ R: p& @
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5