「51nod 1860」BigPrime

我们把所有大于整数 $p$ 的质数称作大质数。

现在我们要统计区间 $[a,b]$ 中有多少数其至少有一个约数是大质数。

Constraints

$p\leq 10^6$ ， $a\leq 10^9$ ， $b-a\leq 10^8$

Solution

先把 $2$ 至 $p$ 所有质数预处理出来。记第 $k$ 个质数为 $p_k$。令 $f(x,y,b)$ 表示 $[x,y]$ 中所有质因子不大于 $p_b$ 的数个数。

分以下几种情况：

若 $x>y$ 则 $f(x,y,b)=0$

若 $b=0$ 且 $x=1\leq y$ 则 $f(x,y,b)=1$

若 $x=y$ 则暴力分解 $x$ 看是否满足。（可以部分预处理）

若 $y\leq p_b$ 则 $f(x,y,b)=y-x+1$

否则 $f(x,y,b)=f(x,y,b-1)+f(\frac{x}{p_b},\frac{y}{p_b},b)$ （上取整）

最后一种情况的意思是，当前 $[x,y]$ 中质因子不包含 $p_b$ 的数。后一个是至少包含一个 $p_b$ 的数，可以把 $p_b$ 除下去以后递归求解。

以上是官方题解。

以下是另一种写法，原理基本一致。

令 $f(x,y,c)$ 表示在 $(x,y]$ 这个区间中所有质因子均不小于 $p_c$ 且不大于 $p$ 的数个数。

枚举第 $c$ 个及其后面的质数，递归计算 $f(\frac{x}{p_c},\frac{y}{p_c},c)$ 并累加。由于需要特殊处理 $1$ 的情况，当 $x=0$ 时 $ans$ 初值为 $1$ 。其余处理细节详见代码。

Code

#include<cstdio>
#include<algorithm> 
#include<cstring>
#include<cmath>
#define LL long long
using namespace std;
const int N=1e6+5;
int p,a,b,cnt,limit,pri[N];
bool np[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int f(int x,int y,int c)
{
	if(x==y)return 0;
	int ans=(x==0);
	while(c<=cnt&&1ll*pri[c]*pri[c]<=y)ans+=f(x/pri[c],y/pri[c],c),c++;
	ans+=upper_bound(pri+c,pri+cnt+1,y)-upper_bound(pri+c,pri+cnt+1,x);
	return ans;
}
int main()
{
	p=read();a=read();b=read();
	for(int i=2;i<=p;i++)
	{
		if(!np[i])pri[++cnt]=i;
		for(int j=1;i*pri[j]<=p;j++)
		{
			np[i*pri[j]]=true;
			if(i%pri[j]==0)break;
		}
	}
	printf("%d\n",b-a+1-f(a-1,b,1));
	return 0;
}