数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第四题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:53
标题:
2019第十届蓝桥杯B组决赛题解第四题
2019第十届蓝桥杯B组决赛题解第四题
9 ?' g5 e# r" k. Z/ x+ J
% A: @% H4 C4 I. l$ S( {5 X1 Z
题意: 寻找有100个约数的最小数
- q6 Y9 @! Q+ \: V/ o$ M8 E
思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
5 O, o8 a+ ?7 @/ f* G
/ i8 `4 v' G* t N
结果:45360
- u3 r7 g* ^! W" o
! w0 d; A" x M& V" l
代码:
/ i7 k4 ?4 Z! O* \; W$ t2 P
/ H* C" O" t5 ]* V7 h q! E
#include<bits/stdc++.h>
9 l/ c) X1 }$ a' `! [6 F8 |
#define mem(a,b) memset(a,b,sizeof(a))
" A# m. }! c% |. p
using namespace std;
/ G, G- J# x6 h% }- [3 t) _$ R
typedef long long ll;
% F; L3 H9 ~5 R# r3 G0 Q8 t! z3 q
const int inf = 0x3f3f3f3f;
, C0 ~: R8 ? [+ u6 D) a" E
const int maxn = 3e5+55555;
6 `' g9 ^% L! _; `- G8 F, D
const ll mod = 998244353;
3 O( i- H! P9 {: p }( z$ H
const double eps = 1e-7;
8 W2 x3 x( J& Q1 b( F' ?% K
1 Y# ?2 Y' z9 u8 `8 ^
bool vis[123456];
! u3 U* d3 D8 q8 h5 m' f: ~
vector<int>prime;
) y5 P+ F" H& T( L
. a2 Y8 J$ y. A) G& U; E
void init() { //素数筛
]7 w8 b8 `9 @
for(int i = 2;i<= 30000;i++) {
" t! X+ B! K; F1 I; I
if(!vis
) {
' G) `+ w6 T" i- `# n. ~ n6 ]
for(int j = i*i;j<= 30000;j+= i) {
, F9 j w7 f( p: c! U% w; z& D
vis[j] = true;
( r B' W8 d% C$ b# k3 s* P
}
) H5 N$ }& e4 r/ j3 V
}
. E0 M4 g7 V; ~/ s
}
3 l. H( ~3 Y: S* t2 u
for(int i = 2;i<= 2019;i++) {
1 |7 V8 s- i5 \" \/ v
if(!vis
) prime.push_back(i);
" r9 u X$ _4 [# Y* n
}
3 t8 N4 x. ^/ W; W9 E: O/ Z) T. V
return ;
9 p1 |! t' i4 F; b9 V* N8 B" i
}
; Z1 L( N8 J/ C3 u
$ P0 y* L. u" h
int cal(int x) {
( n2 ?4 |( z4 F: P' G4 y* ]: H. N
int num[123];
: U0 J5 X$ x% ^" Z0 `4 S. t# ~
mem(num,0);
, v, @3 _( S/ ^- q5 Z
; n4 X* d/ q8 i' G+ t% d9 @/ t
int k = prime.size(),cnt = 0;
8 B% O; J; B# t+ D9 a- G
for(int i = 0;i< k;i++) { // 分解素因子
* y% X9 k$ p- p. ^
if(x%prime
== 0) {
2 C7 W S1 |- Y( N; W% M. e. V
cnt++;
8 t7 R6 G1 F- U. d- L
while(x%prime
== 0) {
( L! z; B& U! ]( a
x/= prime
;
; U/ `- q. [! @' [8 Z [ j
num[cnt]++;
" D* p, |: Z" ]0 \3 F6 M3 q
}
* z: k& b1 Y3 ]' s
}
% x$ m) \/ {& n2 E; m
}
3 X7 `* z! _8 d. Y0 V& q0 d
int ans = 1;
8 u- E1 X* B3 o* O' p
for(int i = 1;i<= cnt;i++) { //计算因子总数
* J. f I A0 l/ [/ i4 r% I
ans*= (num
+1);
8 ^3 W( j$ T8 X8 Q" t" B% m7 b' {
}
% V5 m$ Z4 I* Z# W+ I( Q% y6 H
return ans;
+ x: l% i3 {+ R% l; T3 a$ w
}
6 Y( f8 b8 x/ x/ p3 d
+ q! P* m9 i# i
int main() {
" y. u. _$ F9 Y( q9 m% d9 w
init();
. \4 x0 X2 F! j: `" o/ Q4 ~: b5 ^
for(int i = 99;i<= 1000000;i++) {
. t0 v N" ~8 D0 a& u
if(cal(i) == 100) {
! ]0 e! k7 x8 y2 R- E
cout<<i<<endl;
1 E: I1 Q' h/ Q- X1 Y" t6 m
break;
) ^ \, C& H- _
}
1 R" L- n& U7 {; E4 e X: S' s
}
. ^% O, K/ x6 Z) R9 N$ h
/ r2 m9 u" }1 f4 s2 t4 q t
return 0;
& u3 O3 l. p. W
}
6 D; j* A: W( h) V
---------------------
8 h2 ^" m8 }- R
作者：nka_kun
) G. H* @" c7 `- k& }1 `) U* z
来源：CSDN
L1 z4 N3 |1 [. h
" a: {8 n4 j+ r. [
: M; D& Y+ p) |% F+ }) L0 N
% a. F- ?3 I8 e9 c
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5