题解 P5946 【[POI2002]B-Smooth 数】
hsfzLZH1
·
2020-03-14 15:09:25
·
题解
题目大意
求 [n,n+m] 中最大质因子小于等于 B 的数的个数。
1\le n\le 2\times 10^9,1\le m\le 10^8,1\le B\le 10^6
暴力
用线性筛处理出小于等于 B 的所有质数。枚举 [n,n+m] 的每个数，分解出该数所有小于等于 B 的质因数，如果最后剩下的值是 1 ，说明其最大质因子小于等于 B ，计入答案。时间复杂度 O(B+m\pi(B)) ，空间复杂度 O(B) 。
另一种方法是，一次性分解 [n,n+m] 的所有小于等于 B 的质因子。构造数列 a_i=n+i-1 。枚举小于等于 B 的质数 p ，每次将 a 中所有 p 的倍数除以 p ，直到没有 p 的倍数。最后 a 中 1 的个数即为答案。时间复杂度 O(B+m\log B) ，空间复杂度 O(B+m) 。
正解
考虑优化第二种暴力。我们可以用递归的形式来模拟分解所有小于等于 B 的质因子的过程。令P_i 表示从小到大第 i 个质数， f(c,l,r) 表示在 [l,r] 中分解出所有的前 c 个质数后，剩余 1 的个数。
有 f(c,l,r)=f(c-1,l,r)+f(c,\lceil \frac l {P_c}\rceil,\lfloor \frac r {P_c}\rfloor)
注意一下一系列边界条件：
若 $r\le P_c$ ，则最终 $[l,r]$ 都会被分解到 $1$ ，直接返回答案 $r-l+1$ 。
若 $c=1$ ，则返回答案 $\lfloor \log_2 r \rfloor-\lfloor \log_2 (l-1)\rfloor$ 。
若 $l=r$ ，则直接分解 $l$ 的质因数，并返回答案。
该算法的时间复杂度上界为 $O(B+\pi^2(B)\log m)$ ，实际会更优。
还有一个优化：预处理出小于一个值 $w$ 的所有数的最大质因子。这样当 $r\le w$ 时，直接 $O(r-l+1)$ 求出答案即可。
### 参考代码
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
const int maxn=10000010;
int n,m,b,cur,pri[maxn],cur2,pri2[maxn],maxp[maxn];
bool tf[maxn],tf2[maxn];
int f(int c,int l,int r)
{
if(r<=pri[c])return r-l+1;
if(c==1)
{
return (int)(log(r)/log(2.0)+1.0+1e-6)-(int)(log(l-1)/log(2.0)+1.0+1e-6);
}
if(l==r)
{
int t=l;
for(int i=c;i>=1;i--)while(t%pri[i]==0)t/=pri[i];
if(t==1)return 1;return 0;
}
return f(c-1,l,r)+f(c,(l+pri[c]-1)/pri[c],r/pri[c]);
}
int main()
{
scanf("%d%d%d",&n,&m,&b);
if(b==1){if(n==1)printf("1\n");else printf("0\n");return 0;}
for(int i=2;i<=b;i++)
{
if(!tf[i]){pri[++cur]=i;}
for(int j=1;j<=cur&&i*pri[j]<=b;j++)
{
tf[i*pri[j]]=true;
if(i%pri[j]==0)break;
}
}
for(int i=2;i<=10000000;i++)
{
if(!tf2[i]){pri2[++cur2]=i;}
for(int j=1;j<=cur2&&i*pri2[j]<=10000000;j++)
{
tf[i*pri2[j]]=true;
if(i%pri2[j]==0)break;
}
}
for(int i=1;i<=1000000;i++)maxp[i]=i;
for(int j=1;j<=cur2;j++)
{
for(int i=pri2[j];i<=1000000;i+=pri2[j])while(maxp[i]%pri2[j]==0&&maxp[i]!=pri2[j])maxp[i]/=pri2[j];
}
printf("%d\n",f(cur,n,n+m));
return 0;
}
```