数学建模社区-数学中国
标题:
2019第十届蓝桥杯B组决赛题解第四题
[打印本页]
作者:
杨利霞
时间:
2019-6-28 15:53
标题:
2019第十届蓝桥杯B组决赛题解第四题
2019第十届蓝桥杯B组决赛题解第四题
& N( {( C4 ]+ v" n; g
/ j% B# A5 p4 l0 h
题意: 寻找有100个约数的最小数
1 a6 B- k% h/ U) o8 N. B
思路: 本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)
0 t9 l7 b4 V% Y/ z; q
2 }* Y1 |8 t, ]2 A6 R
结果:45360
+ q! P+ s0 }6 w
+ O- q# X. l* u3 \2 Y
代码:
: T& g3 U5 `0 b: F6 Z: j( Z' c5 [
+ d7 a& G5 g5 ~; K9 o& j) C
#include<bits/stdc++.h>
6 E B8 w3 Q" j- A- s
#define mem(a,b) memset(a,b,sizeof(a))
# ~( F( J; j: ]4 {8 ~3 N8 Q1 D* G
using namespace std;
! |, P( p- `5 p7 u1 _8 { b
typedef long long ll;
8 t9 }( e4 ^/ @( F5 p4 V
const int inf = 0x3f3f3f3f;
9 U- j. z. @& g w
const int maxn = 3e5+55555;
6 s2 x1 _. R7 p1 ?
const ll mod = 998244353;
% s1 i) j+ V3 L7 @) ~/ h7 C
const double eps = 1e-7;
8 f" Q( h7 P8 Y1 S0 g& T
6 d$ b6 d3 J$ [) h6 s4 i
bool vis[123456];
6 t2 h2 n! z6 N
vector<int>prime;
# T" |8 b+ ~0 Q0 Y
5 @2 x. l9 J/ F, i7 [+ T2 L, w
void init() { //素数筛
2 R! c) ]( h0 t) ^
for(int i = 2;i<= 30000;i++) {
( K9 K5 ?$ y7 H' s' H
if(!vis
) {
$ o% a6 O3 o/ U3 M. E
for(int j = i*i;j<= 30000;j+= i) {
0 i- T4 }0 W2 `+ m% Q
vis[j] = true;
9 N1 U8 [& r& I' j
}
+ b3 _( Z7 B5 O v5 _, |" ^
}
1 e: O$ q# N- d/ M! a
}
! I$ U8 w! C% U
for(int i = 2;i<= 2019;i++) {
# g! `2 c3 m& _* G2 G3 n6 _
if(!vis
) prime.push_back(i);
+ S8 d n% Y3 I- \+ @2 `1 N5 s% `
}
1 |& }. F& q' `* ^9 K' |# `
return ;
6 j4 A) T0 \) F0 ?. O5 e6 e6 v5 w0 Y
}
( R* ^. U" E2 H. N
$ B# }- L0 t- s; q3 r( w
int cal(int x) {
1 ?% _# J/ H" j0 H
int num[123];
1 {/ [; N3 `) l# |
mem(num,0);
# P/ \) }' \8 z$ o
% n/ r/ ?( h9 z( L0 j
int k = prime.size(),cnt = 0;
/ I5 n+ c+ Y& b { y1 n" u& y# \
for(int i = 0;i< k;i++) { // 分解素因子
7 s. h4 ~ A' j
if(x%prime
== 0) {
& E# ~( B& {& `
cnt++;
4 v/ P1 l) Q# [1 `! c- b% h
while(x%prime
== 0) {
8 \9 e& Q' E' d! |% f* t
x/= prime
;
Q3 d- V. ]3 r9 Z6 m
num[cnt]++;
$ l4 D8 W: a) e. r! r4 O" s) Z
}
. Y8 ]# V* v3 x0 ?' {
}
5 V0 \, k9 i& n& H/ s+ f
}
4 m5 e+ C5 |7 e1 m2 O" s! p' N' T
int ans = 1;
7 q& t9 L2 u' Y
for(int i = 1;i<= cnt;i++) { //计算因子总数
5 q( k0 A' r @* y( A1 {
ans*= (num
+1);
6 r7 Q( }- p, U" B) S( h7 l% E
}
7 X2 X" s H3 s1 y
return ans;
. N: R! x) q) ]$ d- G
}
% i t. q7 q' \% x/ }0 u% T8 {
& q: Z: s! R% B4 s9 ^1 T+ s) S
int main() {
& H. V: \) `3 r4 `3 F* c5 {
init();
' _: F( O1 B* R5 v! ` K1 k6 i! }6 P) r
for(int i = 99;i<= 1000000;i++) {
9 r9 x B% s1 e+ Y7 B
if(cal(i) == 100) {
# W% h2 L o3 c% _7 d9 p
cout<<i<<endl;
( m4 S$ X: p) J5 T* C% q' s
break;
' O+ s( K( Y, a
}
. W' s+ [; E$ c h9 p
}
9 j( n4 L. s& D: \! m# k
. n0 C/ c2 r4 P7 }$ M( [
return 0;
6 ?) b2 V. P% Y- I% W& U9 p
}
6 Z4 k5 r1 G* @2 @
---------------------
4 c" Q/ m) l0 j: L, A' }- w8 T) Y: i8 Q
作者：nka_kun
. c ~5 I5 }, `/ w L- Q& d
来源：CSDN
) W, f# J. @! W. c, L
( Q8 I1 a+ E/ X' ~, L
: j( |6 L9 G( s. R& X$ k
; N+ F6 h+ f7 I% d/ ?
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5