题目描述
AcWing 198. 反素数 - AcWing
样例
结论
1 如果一个数字m 它的质因子p1,p2,p3,p4,p5 它每个质因子的个数N1,N2,N3,N4,N5 那它的约数个数就为N1xN2xN3xN4xN5;
2 如果要是上面要使上述的m尽量的小，那它的每个质因子必然是紧挨着的，同时对应的质因子的N1>=N2>=N3>=N4>=N5
顺便说一下2∗3∗5∗7∗11∗13∗17∗19∗23∗29∗3>2*10^9 所以代码里面的线性筛没必要，枚举就可以了
如果每个质因子都一样大 那很明显 我尽量的把每个质因子的数量分为两分同时然后质因子也尽量多，那约数个数也就是
指数级最大，但是事与愿违，质因子分的多，同时拆分出的最大质因子也会变得很大所以要深搜，找出一个最佳的分配方案
时间复杂度
C++ 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include<bits/stdc++.h>
using namespace std;
int cnt=0;
int primes[100000];
bool st[1000000];
int qmi(int a,int b){
int ans=1;
while(b){
if(b&1) ans*=a;
a*=a;
b>>=1;
}return ans;
}
void init(int k)
{
for(int i=2; i<=k; i++)
{
if(!st[i]) primes[++cnt]=i;
for(int j=1; j<=cnt&&i*primes[j]<=k; j++)
{
st[i*primes[j]]=1;
if(i%primes[j]==0)break;
}
}
}
int mm=0;//最多约数的数量
int n;
int cc=999999;//递归找到当前状态下 出现最多约数的最小值
void dfs(int num,int k,int f,int ans)
{
if(ans==mm)cc=min(cc,num);//如果当前约数的数量等于目前最大的约数数量 那cc（也就是答案）要取两者最小
else if(ans>mm){//如果约数数量大于当前最大的 那就更新答案
mm=ans;
cc=num;
}
for(int i=1;i<=f;i++)//深搜下一个质因子
{
int h=qmi(primes[k+1],i);//快速幂也没必要 我是小丑
if((long long)h*num>n) break;//我的写法要加longlong 不然会爆
dfs(num*h,k+1,i,ans*(i+1));
}
}
signed main()
{
init(100010);
cin>>n;
for(int i=1; i<=30; i++)
{
if(1<<i>=n)break;
dfs(1<<i,1,i,i+1);//当前数值，多少个质数因子，最后一个数的次方，约数个数
}
cout<<cc<<endl;
}
|
所以呢就别不快乐。