数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第四题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:53
标题:
2019第十届蓝桥杯B组决赛题解第四题
2019第十届蓝桥杯B组决赛题解第四题
7 h e9 i# X0 U7 H1 h: n
Q9 z' M. w- Q. K$ @2 v7 t
题意: 寻找有100个约数的最小数
9 X9 @7 c1 m! @8 W2 I
思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
0 l& W. L% I! n; D# K
0 q! q, j2 H, L) X( r
结果:45360
1 F# ^# _3 s0 [1 H- X
! D9 l2 E" W+ c" [6 b# o
代码:
8 }2 R* y- x, Z
z! U. f7 I$ r2 r" e0 }
#include<bits/stdc++.h>
. o' n/ o) m: t2 k0 t( r ~
#define mem(a,b) memset(a,b,sizeof(a))
5 v: K: R) U) _) d4 [
using namespace std;
7 f& ^' b2 `7 c
typedef long long ll;
4 O2 s* P0 o1 `+ J4 \0 {. {# Q
const int inf = 0x3f3f3f3f;
! M' S9 j0 q7 p% ?3 \8 \. e
const int maxn = 3e5+55555;
& N- J" y: v5 x! F/ w8 r
const ll mod = 998244353;
' d5 M5 t5 B* ]; c3 p! S
const double eps = 1e-7;
5 ]& q1 \! u/ ]$ D, A: B
: R" ]; [& V& o3 G* ^& j
bool vis[123456];
" }/ o% Z4 M& D9 K" ]! t
vector<int>prime;
/ n: d8 M9 M9 B6 `
7 E3 W" o/ B0 z# w, n" V
void init() { //素数筛
' d4 k1 K% P. j) C- _/ ?# q
for(int i = 2;i<= 30000;i++) {
& B9 b8 @4 d- X/ H' t% e' G% ^
if(!vis
) {
5 ]( Y0 V3 s( s8 n* O( u
for(int j = i*i;j<= 30000;j+= i) {
: }2 X A* h4 u( g
vis[j] = true;
. B+ |/ e, @. l: ^
}
3 o' ^7 X5 |9 R9 {
}
2 T9 ]6 P8 T( h D
}
) W0 d8 E5 M5 G1 d8 B( [( C
for(int i = 2;i<= 2019;i++) {
! _" b w$ Q6 h1 R) s
if(!vis
) prime.push_back(i);
* m/ [4 m2 t, N! H
}
$ Q( X2 u6 z) c" ^5 C$ S* m+ j' j: g
return ;
2 a' ^6 [% X8 O3 C# m" `* |: a
}
. R' e+ ~) D/ K0 w- q5 e& b6 [
. ^/ e [& B) i+ Z v+ ?
int cal(int x) {
, p5 ?4 G& w+ H" U
int num[123];
: e3 c: `$ s' f+ S0 k0 d* P
mem(num,0);
5 A. w5 E3 B' `) j
% M& F+ K3 X/ e7 I% w2 v
int k = prime.size(),cnt = 0;
" U0 B+ f Z0 }% w" ?. [
for(int i = 0;i< k;i++) { // 分解素因子
# \" }4 s/ A9 ~' _/ I
if(x%prime
== 0) {
" P6 M! a+ U& n/ d+ w
cnt++;
* ]& K8 @( c5 s2 d! l
while(x%prime
== 0) {
4 a. e8 m- s) r$ s1 q/ _
x/= prime
;
* {& E3 \; N: @
num[cnt]++;
$ D) b- L! j+ ]3 N2 T
}
s- z( d5 f( M7 B" |4 e
}
7 \, l+ B' T9 T* v6 x3 r
}
) ^! G' J! `1 ?4 R% V4 ]
int ans = 1;
5 ~( ?8 F. K% }2 W
for(int i = 1;i<= cnt;i++) { //计算因子总数
$ d7 o' f" g2 a: G& a+ I, w
ans*= (num
+1);
N( U% b* Z! A3 ]9 Y0 `$ U
}
! E: N$ f3 b1 c3 U: Y
return ans;
. z8 B$ F" \ O) D( l( X3 m/ [
}
" x i4 U# g K) T, H- p6 z, ?! h
+ R5 @3 R3 V2 H% v8 U7 d9 a
int main() {
$ S! H O* U J
init();
" [; A G( i2 u4 l4 }8 @( ^: ^0 \, U
for(int i = 99;i<= 1000000;i++) {
/ R4 {! w! s. o9 g' w0 P
if(cal(i) == 100) {
* I* }1 x6 S- T+ ~+ r
cout<<i<<endl;
) y/ ^. d6 |$ r
break;
. G8 Y) z& h# [3 s8 g p/ U
}
* x5 _- r, W# w1 ^& E$ H
}
* L& G; L% N+ z9 D
% h: o1 i! }3 B; U* E1 R2 k3 o
return 0;
% B* m: m4 S/ d
}
: o4 ~) V2 R- B8 s0 G; T+ T! l2 D8 G
---------------------
" v$ B* F7 D# a* j+ m" G- ]
作者：nka_kun
+ b Q7 o' A" Y
来源：CSDN
6 t2 F# U$ C$ k( b* _; |
+ N/ P; ~7 N% B9 f3 \
7 C% s. G: n) _, ^
) y; I3 m$ e$ t6 R. T# e' E W! V
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5