题解：B3969 [GESP202403 五级] B-smooth 数

思路：

定义一个数组存这个数最大的质因数。

如何存，枚举每一个小于 $n$ 的质数，再枚举它的倍数，但是在枚举倍数时要注意如果第二个数字大于了第一个数字且第二个数字是质数那么先跳过，且第一个数字乘第二个数字要是大于 $n$ 那么退出这一层循环写进判断条件里，代码如下。

for(long long i=2;i<=n;i++){
		if(zs(i))//注意 i 要是质数
		for(long long j=1;j*i<=n;j++){//枚举 i 的倍数
			if(j>i&&zs(j))continue;// 如果 j 大于 i 且 j 是质数 那么说明 i*j 这个数的最大质因数不是 i 直接跳过后面再赋值
			bj[j*i]=i;
			//cout<<i*j<<"\n";// 测试
		}
		else continue;//i 不是质数跳过
	}

标记好了后，定义一个存的变量变量赋值为一，因为虽然一没有质因数但是还是要加上，然后枚举从二到 $n$ 中有多少个的最大质因数是小于等于 $B$ 的就可以了，为什么从二开始枚举因为一已经在定义时加上了，代码如下。

long long ans=1;
for(long long i=2;i<=n;i++){
		if(bj[i]<=b)ans++/*,cout<<i<<"\n";*/;
	}

然后输出就可以了。

完整代码：

#include<bits/stdc++.h>
using namespace std;
long long n,b,ans=1;// 定义移到主函数外了
long long bj[1000099];
bool zs(long long x){// 判断质数
	if(x==1)return 0;
    if(x==2||x==3)return 1;
    if(x%6!=1&&x%6!=5)return 0;
    for(int i=5;i*i<=x;i+=6)if(x%i==0||x%(i+2)==0)return 0;
    return 1;
}
int main(){
	cin>>n>>b;// 输入
	for(long long i=2;i<=n;i++){
		if(zs(i))
		for(long long j=1;j*i<=n;j++){
			if(j>i&&zs(j))continue;
			bj[j*i]=i;
			//cout<<i*j<<"\n";
		}
		else continue;
	}
	for(long long i=2;i<=n;i++){
		if(bj[i]<=b)ans++/*,cout<<i<<"\n";*/; 
		//if(bj[i]==0)cout<<i<<"\n";// 测试
	}
	cout<<ans;// 输出
	return 0;
}