查看: 2109|回复: 0

2019第十届蓝桥杯B组决赛题解第四题

[复制链接]

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2019-6-28 15:53 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

2019第十届蓝桥杯B组决赛题解第四题

题意:  寻找有100个约数的最小数
思路:  本质上就是用了素因子分解，假设分解出来的素因子有4种，分别有x1个,x2个,x3个,x4个，第i种因子可以选0个或者1个或者2个或者···或者xi个,那么因子总数为(x1+1)*(x2+1)*(x3+1)*(x4+1)

结果:45360

代码:

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5+55555;
const ll mod = 998244353;
const double eps = 1e-7;

bool vis[123456];
vector<int>prime;

void init() { //素数筛
for(int i = 2;i<= 30000;i++) {
      if(!vis) {
1 u6 m4 d$ A) b6 I; {7 y; G0 n% q          for(int j = i*i;j<= 30000;j+= i) {# T  d- ^8 q0 l" Y! A& d
            vis[j] = true;
2 f  J8 O: O# y          }6 r' f+ N- C0 U' T& K/ S* Z
      }
* T: v, f0 X) C( E5 v( F; \ }
' U0 |( V; U. s6 T+ U for(int i = 2;i<= 2019;i++) {. p8 [5 E2 d* \, `
      if(!vis) prime.push_back(i);
8 l3 Q$ y* g( N; D! R: N3 F, E }0 V: V2 k! o% b
return ;& u# \6 U" D9 ]6 v* U7 d- f" F7 V
}2 W$ t3 D" R2 @% B0 B
6 _. b0 I1 w3 h: Z+ u* t! _$ K% C
int cal(int x) {
6 Q: S( k# Y$ w, \4 ^) z int num[123];
, R. t* t5 q' \( W$ P# N8 S mem(num,0);+ |0 _5 L) P: `1 `1 G) x& Z/ ]- Y
6 h& ]  p# ]. i0 ]7 f; p8 X
int k = prime.size(),cnt = 0;
7 W( f6 v( p) r/ [6 l& }" X& s for(int i = 0;i< k;i++) { // 分解素因子
# t; B) `: B7 Z( ?       if(x%prime == 0) {! R( I4 j. x* L/ C$ i4 U& o( p6 b
         cnt++;
7 p( J6 l* z2 b* }( r! c+ g4 Q' R          while(x%prime == 0) {0 b. ~& O# ^% Q
            x/= prime;3 k/ d0 y8 {! g; v" O) `5 o: x
            num[cnt]++;% ?' M" Q7 }5 ~. S
         }
( `4 N7 N. L+ V9 H3 p# ]9 b       }
' z+ W0 d8 M) W; D: `0 w4 _ }4 H6 B% U9 T  p! r8 P. D
int ans = 1;* q/ Q* l9 `. O5 m% c
for(int i = 1;i<= cnt;i++) { //计算因子总数
) S6 c, F) {4 V+ C       ans*= (num+1);
$ r) T; ]2 F5 B2 \2 g }+ y4 s# q0 b5 U# V9 V; P! P
return ans;4 n, h& r+ Z0 c* G3 F: k
}5 W0 A2 n9 s4 o  ?. C. Y# b7 _+ }
, X3 q! }6 {8 v( Z" G+ @9 o
int main() {
) Z' m: k; R; y( }& m  P7 `1 s1 C! q init();: w' z4 R. k( r" [5 [
for(int i = 99;i<= 1000000;i++) {
8 L" ~8 W; M" w) T" ~" ^       if(cal(i) == 100) {
) t6 J, e3 x; d; N6 N6 y0 w7 F2 |! i          cout<<i<<endl;
' J' w9 S4 v8 m5 \! {' B          break;: ]; c4 H* m! T; P4 p9 p- v0 W
      }
( J, U- q5 g1 Z# u( h6 K }
% d# e2 U! y/ R6 |
8 f/ `" k! I7 y! X/ Q% Y  k return 0;
( e3 U, [3 c+ I8 ]7 k0 W6 ?: E2 e6 a, Q}
" O7 h0 ?$ N: v* m  V) _* n7 |--------------------- 9 Q' G/ A5 g* O$ E0 o
作者：nka_kun
9 O' z7 z! O+ {, G来源：CSDN
3 p: @6 a! ~: a0 q/ ?0 Z8 k8 G) s& t- \" k' C8 U* l% {
% U7 G, n5 Q; ~# k
! V  o9 N: S4 J* J, E) x% t