查看: 2171|回复: 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) {
! ~: B* l8 ]8 `$ [' h+ P. r# `          for(int j = i*i;j<= 30000;j+= i) {
. v9 ?" ]/ G/ @. y4 B4 g9 r2 D* Z             vis[j] = true;; v: m2 z- |8 @
         }- X5 G8 K7 p  L) P$ i
      }
% ]$ `$ s* v1 l4 n: e }- Z& r7 g. q6 d" Q4 @- E2 U
for(int i = 2;i<= 2019;i++) {
' i/ `0 ?; u9 V  n$ c/ I       if(!vis) prime.push_back(i);
: F' \! l0 [4 e' |; i2 O }
3 P2 Y4 A4 C& ~0 l return ;
. i. }% t3 G* V6 F6 B* D}
/ p; {1 p0 }1 E1 Q! P& [% Z+ L1 T5 Y, x3 z
int cal(int x) { & J0 A) B4 Z! Y# c5 `0 i! f
int num[123];7 |) n$ @6 p: i( u' B6 U$ P
mem(num,0);
& @; w; I0 E$ }* S/ l+ {9 z
% P8 a7 \: E. `7 } int k = prime.size(),cnt = 0;
$ W# F6 u, ^6 ?. l+ H; J$ j for(int i = 0;i< k;i++) { // 分解素因子! p) Z' X/ m+ F/ E$ b/ @
      if(x%prime == 0) {$ U8 o8 L# O+ y" ]3 p
         cnt++;6 D1 {: O, |4 x8 ?- S
         while(x%prime == 0) {( g' \. v2 y( b) V7 U1 b) H
            x/= prime;3 ]& p- ~, m# n3 o+ `8 x
            num[cnt]++;! s8 L% l" i5 z3 J/ R
         }  |( b# V3 X% ?4 v4 R4 n! d
      }* z' ?, A" P4 `& }6 l
}
3 u8 [* W# U* F; v; K: d# r. ], { int ans = 1;1 l4 Z& ^( |: n3 \
for(int i = 1;i<= cnt;i++) { //计算因子总数8 b$ Z- @5 F& h$ h
      ans*= (num+1);- P# K" t: U4 _7 }6 g. G4 b
}  f6 v. m+ R4 c- k; `
return ans;: f7 \# J+ v8 U1 h( Q) l3 B9 U
}+ ~9 z, {" v' _- k% ?3 _* U  I
: l3 i% J; ^- p+ @- ?+ Q; Y1 {
int main() {8 B: S  {' E( L% c, ]
init();
. ~# C" d; q. O1 q$ S# B for(int i = 99;i<= 1000000;i++) {: M' c! q" A9 Y* c
      if(cal(i) == 100) {
6 I5 x  Q$ {# T& g          cout<<i<<endl;
+ f: z/ N+ B1 F9 H4 S7 y# e          break;
8 Y. S* u% ?# N2 d9 M+ }& \* x8 {1 r       }
6 V- C) \* A- u  P$ t% [$ {; q }. p0 h  n' j2 s

: L0 b. z7 b; k2 `$ W return 0;
- J/ G! |9 I5 V: b, f$ ]1 I* G  t}
! \. @+ Z, o+ j( Z) \--------------------- ; a8 w9 K# J( D
作者：nka_kun * C: U2 E$ g, W5 ?: b+ ]& V
来源：CSDN
' f' e2 I+ t. ?: Q" {6 s8 Z
* h5 l4 Z' u8 q( u" q8 \+ _+ o+ M% z6 e% O
. k$ P- {, Z7 N* F( ]6 a