出题人题解 | #a-贝利福斯数#

原题解链接：https://ac.nowcoder.com/discuss/149978

考虑使用类似线性筛的方法，从小到大枚举每个a-贝利福斯数 $ii$ ，然后从小到达枚举每个a-贝利福斯素数 $xx$ ，标记 $i\times xi\; \backslash times\; x$ ，如果 $i\mathrm{m}\mathrm{o}\mathrm{d}x=0i\; \backslash bmod\; x=0$ ，则结束枚举。

这个做法正确性是显然的，但是由于a-贝利福斯数并不满足唯一分解定理，可能存在多种分解成a-贝利福斯素数的 方式，所以一个数可能被标记多次。但是重复标记的次数不是很多，经检验，至少当 $n=2\times 10^7,a\le 10n=2\; \backslash times\; 10^\{7\},\; a\; \backslash leq\; 10$ 时，这 个次数是 $10^{6}10^\{6\}$ 级别的，所以这个算法至少在本题数据范围内还是 $O(n)O(n)$ 的。

至于判断哪些数是两个a-贝利福斯素数的乘积，只要暴力枚举两个素数就好了，复杂度显然不高于前面的筛法。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=2e7+5;
bool is_not_pr[N],can[N];	
int pr[N],pcnt;

int a;
int mul(int x,int y)
{
	return a*x*y+x+y;
}

int main()
{
	int n;
	cin>>a>>n;
	n=(n-1)/a;
	rep(i,1,n)
	{
		if(!is_not_pr[i])pr[++pcnt]=i;
		for(int j=1;;++j)
		{
			int x=pr[j],now=mul(i,x);
			if(now>n)break;
			is_not_pr[now]=1;
			if((a*i+1)%(a*x+1)==0)break;
		}
	}
	rep(h1,1,pcnt)
	{
		int i=pr[h1];
		rep(h2,1,pcnt)
		{
			int now=mul(i,pr[h2]);
			if(now>n)break;
			can[now]=1;
		}
	}
	int ans=0;
	rep(i,1,n)
	if(can[i])++ans;
	cout<<ans;
}