数学建模社区-数学中国

标题: 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
结果:453603 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* Iusing namespace std;
7 u4 {( \. p* I; atypedef 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% Mbool 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& hvoid 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. {  Oint 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: fint 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