P1221 最多因子数 题解
SegTree
·
·
题解
不保证能通过数据范围下所有数据。
[将素数筛到 $50000$ 时的记录](https://www.luogu.com.cn/record/79789362)。
[题目传送门。](https://www.luogu.com.cn/problem/P1221)
## 题目分析
如果直接暴力枚举上界与下界的因数个数并比较，复杂度过高，不可接受。
考虑直接打表输出 $1$ 到 $10^9$ 的因数轻轻松松 `MLE` 且超过 $50\text{KB}$。
考虑分段打表。
以 $10^6$ 为一段，从 $1$ 一直枚举到 $10^9$，输出的表的第 $i$ 项表示 $10^6\times (i-1)+1$ 到 $10^6\times i$ 中因数最多的数及它的因数个数。
但是你会发现程序运行得很慢……所以可以先写一个程序计算 $1$ 到 $3\times 10^4$ 中的所有质数，打表存在打表程序里，枚举时直接从 `pr[]` 数组中的质数判断，减少了运行时间，之后就从 $3\times 10^4+11$ 开始枚举。（而这时该数可能已经变小很多）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int pr[]={};
inline int fun(int a){
int ans=1;
for(int i=1;i<sizeof(pr)/sizeof(int)&&pr[i]*pr[i]<=a;++i){
int cnt=1;
while(a%pr[i]==0)cnt++,a/=pr[i];
ans=ans*cnt;
}
for(int i=30011;i*i<=a;++i){
int cnt=1;
while(a%i==0)cnt++,a/=i;
ans=ans*cnt;
}
if(a!=1)ans<<=1;
return ans;
}
signed main(){
printf("{{0,0},") ;
int l=1,r=1e9,maxn=-1,ans;
for(int i=l;i<=r;++i){
if(fun(i)>maxn)maxn=fun(i),ans=i;
if(i%1000000==0){
printf("{%d,%d}",ans,maxn);
if(i!=r)printf(",");
else printf("}");
maxn=-1;
}
}
return 0;
}
```
最后计算，如果 $\lfloor \dfrac{l}{10^6}\rfloor=\lfloor\dfrac{u}{10^6}\rfloor$，就进行暴力。
否则在将 $l$ 到 $\lceil\dfrac{l-1}{10^6}\rceil\times 10^6$ 和 $\lfloor\dfrac{u}{10^6}\rfloor\times 10^6+1$ 到 $u$ 暴力求解，枚举表中 $\lceil\dfrac{l-1}{10^6}\rceil$ 到 $\lfloor\dfrac{u}{10^6}\rfloor$ 即可。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int pr[]={};
int fun(int a) {
int ans=1;
for(int i=1;i<sizeof(pr)/sizeof(int)&&pr[i]*pr[i]<=a;++i){
int cnt=1;
while(a%pr[i]==0)cnt++,a/=pr[i];
ans=ans*cnt;
}
for(int i=30011;i*i<=a;++i){
int cnt=1;
while(a%i==0)cnt++,a/=i;
ans=ans*cnt;
}
if(a!=1)ans<<=1;
return ans;
}
int a[][2]={};
signed main(){
int l,u,j,maxn=-1,ans;
scanf("%d %d",&l,&u);
if(l/1000000==u/1000000){
for(register int i=l;i<=u;++i){
int x=fun(i);
if(x>maxn)maxn=x,ans=i;
}
}
else {
for(j=l;;++j){
if(j%1000000==1)break;
int x=fun(j);
if(x>maxn)maxn=x,ans=j;
}
for(register int i=j/1000000+1;i<=u/1000000;++i){
if(a[i][1]>maxn)maxn=a[i][1],ans=a[i][0];
}
for(register int i=u/1000000*1000000+1;i<=u;++i){
int x=fun(i);
if(x>maxn)maxn=x,ans=i;
}
}
printf("Between %d and %d, %d has a maximum of %d divisors.",l,u,ans,maxn);
return 0;
}
```
由于代码较长，`pr[]` 数组和 `a[][]` 数组在这里无法给出，请去[这里](https://www.luogu.com.cn/problem/U228570)下载。
评测记录：[不吸氧](https://www.luogu.com.cn/record/79787094)，[吸氧](https://www.luogu.com.cn/record/79787759)。