2019第十届蓝桥杯B组决赛题解第四题
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;
vector<int>prime;
void init() { //素数筛
for(int i = 2;i<= 30000;i++) {
if(!vis) {
for(int j = i*i;j<= 30000;j+= i) {
vis = true;
}
}
}
for(int i = 2;i<= 2019;i++) {
if(!vis) prime.push_back(i);
}
return ;
}
int cal(int x) {
int num;
mem(num,0);
int k = prime.size(),cnt = 0;
for(int i = 0;i< k;i++) { // 分解素因子
if(x%prime == 0) {
cnt++;
while(x%prime == 0) {
x/= prime;
num++;
}
}
}
int ans = 1;
for(int i = 1;i<= cnt;i++) { //计算因子总数
ans*= (num+1);
}
return ans;
}
int main() {
init();
for(int i = 99;i<= 1000000;i++) {
if(cal(i) == 100) {
cout<<i<<endl;
break;
}
}
return 0;
}
---------------------
作者：nka_kun
来源：CSDN
页:
[1]