P1221 最多因子数 题解
反素数
推荐和本蒟蒻博客一起食用
1.定义
"于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。 如果某个正整数x满足：g(x)>g(i)，0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。"
————度娘说的
什么意思呢？用自己的口水话解释一下：对于一个数
2.性质
从反素数的定义可以发现凡是反素数都满足两个性质：
- 性质一：对于所有反素数
x={a_1}^{b_1} *{a_2}^{b_2}*{a_2}^{b_2}*···*{a_k}^{b_k} ,则必有b_1\ge b_3\ge ···\ge b_k
这点很好理解，借助贪心的思想我们思考：首先要让因子数量尽可能的多，只需要把质因数的次数变多，或者质因数变多。但是还得满足让数值尽可能的小，那么就要让小的质因数的次数尽可能的大 - 性质二：一个反素数的质因子必然是从2开始连续的质数
举个例子：
6=2*3,10=2*5 6 和10 因子数目相同，显然6 更小。直接跳过一个小一点的质数，放一个大的质数显然会使数值变得更大。
3.例题
大致思路是：从最小的质数（2）开始用
- deep：枚举到第几个质数了
- arr：当前质数的最大指数（当前指数
\leq 上一个质数的指数） - cur：从开始枚举到当前共有多少因数
- num：从开始枚举到当前所有枚举的质数组成的数（幂之后相乘）
每次
void Dfs(int deep,int arr,int cur,ll num){
if(maxn<cur||(maxn==cur&&num<ans))
maxn=cur,ans=num;
if(deep>8)
return;
for(register int i=1;i<=arr;i++){
num*=prime[deep];
if(num>r)
return;
Dfs(deep+1,i,cur*(i+1),num);
}
}那边界又是什么呢？应该枚举多少个质数呢？（先去看看下面的完整代码吧） 我们注意到有关边界的有四处：
-
if(num>n) 这个好理解：当这次枚举的结果超过范围了，自然不用向下枚举了，return。
-
ll prime[15]={2,3,5,7,11,13,17,19,23,29,31,37};
if(deep>9) 为什么只需要这９(prime[0]~prime[8])个质数呢？ 原因很简单：首先，因为是反素数，所以因数要多，数本身值要小，所以是前9个质数。其次，我们把每9个质数都只取一个，此时组成的数已是223,092,870了，再多1个29的话就会超过范围2,000,000,000了。（其实多算几个也没错） -
Dfs(0,31,1,1); 为什么第一个初值传31呢？ 原因也很简单：第一个质数是2，那最多能选多少个2相乘呢？ ——31个，
2^{31}=2,147,483,648 恰好大于范围。
这。。。这不是暴力吗？？ 要这个干嘛？
if(r-l<=100000){
for(register ll i=l;i<=r;i++){
cnt=0;
for(register int j=1;j*j<=i;j++)
if(i%j==0){
cnt++;
ll temp=i/j;
if(i%temp==0&&temp!=j)
cnt++;
}
if(cnt>maxn)
ans=i,maxn=cnt;
}
}首先，这个暴力的复杂度在一定范围内是可以接受的。问题就来了不是有毒瘤数据 情况，当L，R相距很近时，在这个区间中不存在反素数，但仍有答案。这种数据出现在枚举的区间很小情况下，便可以用暴力解决。至于区间多大时该用暴力，这个没有固定的值，只有根据题的范围来确定，不过我通常用100,000 or 200,000。
AC代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T&x){
x=0;int temp=getchar();bool f=false;
while(temp<'0'||temp>'9'){if(temp=='-') f=true; temp=getchar();}
while(temp>='0'&&temp<='9'){x=(x<<1)+(x<<3)+temp-'0'; temp=getchar();}
if(f) x=-x;
}
ll prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41};
ll l,r;
ll maxn=0,ans,cnt;
void Dfs(int deep,int arr,int cur,ll num){
if(maxn<cur||(maxn==cur&&num<ans))
maxn=cur,ans=num;
if(deep>8)
return;
for(register int i=1;i<=arr;i++){
num*=prime[deep];
if(num>r)
return;
Dfs(deep+1,i,cur*(i+1),num);
}
}
int main(){
read(l),read(r);
if(r-l<=100000){
for(register ll i=l;i<=r;i++){
cnt=0;
for(register int j=1;j*j<=i;j++)
if(i%j==0){
cnt++;
ll temp=i/j;
if(i%temp==0&&temp!=j)
cnt++;
}
if(cnt>maxn)
ans=i,maxn=cnt;
}
}
else
Dfs(0,31,1,1);
printf("Between %lld and %lld, %lld has a maximum of %lld divisors.",l,r,ans,maxn);
return 0;
}