专栏文章

题解：SP8238 NFACTOR - N-Factorful

DDark_Blue_Sky
SP8238题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipctjr6
此快照首次捕获于
2025/12/03 09:54
3 个月前
此快照最后确认于
2025/12/03 09:54
3 个月前
查看原文

题解：SP8238 NFACTOR - N-Factorful

思路分析

我们先用筛法筛出 1∼1061 \sim 10^6 所有的质数。
然后，我们再枚举 1∼1061\sim 10^6 中的所有整数 ii，并用根号级（枚举 1∼n1\sim \sqrt{n} 中所有的素数）的时间算出 ii 的因子个数 ss，并标记 sumi,ssum_{i,s} 为 11。
接着，我们对 sumisum_i 进行前缀和即可求出 sumi,1∼nsum_{i,1 \sim n} 的答案。
最后输入时，只需要输出 sumr,n−suml−1,nsum_{r,n}-sum_{l-1,n} 即可。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[1000005],vis[10000005];
int tot[10000005];
int b[1000005][15];
vector<int> prime;
map<int,int> minn,maxx;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	for(int i=2;i<=1000000;i++){
		if(!vis[i])prime.push_back(i);
		for(int j=1;prime[j-1]*i<=1000000&&j<=prime.size();j++){
			vis[min(i*prime[j-1],1000000ll)]=true;
			if(i%prime[j-1]==0)break;
		}
	}
	for(int asd=1;asd<=1e6;asd++){
		int i1=asd;
		int cnt=0;
		for(int j=0;prime[j]*prime[j]<=i1;j++){
			if(i1%prime[j]==0){while(i1%prime[j]==0)i1/=prime[j];cnt++;}
		}
		if(i1>1)cnt++;
		if(cnt<=10)b[asd][cnt]=1;
	}
	for(int i=1;i<=1e6;i++)
		for(int j=0;j<=10;j++)
			b[i][j]+=b[i-1][j];
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		int n,l,r,cnt=0,ans=0;
		cin>>l>>r>>n;
		cout<<b[r][n]-b[l-1][n]<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...