专栏文章

题解：SP31040 NGIRL - Namit In Trouble

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

文章操作

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

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

题解：SP31040 NGIRL - Namit In Trouble

思路分析

首先，我们理解一下，什么是“恰好拥有 3 个因数”，其中，因为 1≤N≤10101\le N\le 10^{10}，所以必定会有两个因数 11 和它本身。那么显而易见了，剩下一个必定是质数。假设这个数是 nn，那么它可以分解为 a×ba\times b，其中 2≤a,b≤n2\le a,b\le n，要满足这个条件，只可能 a=ba=b。所以，这个数是一个质数的平方。
那么，我们用筛法筛出 1∼1061 \sim 10^6 所有的质数，再枚举筛出来的质数，并将这些质数的平方压入一个数组 ansans 中（从小到大压）。
对于每组测试数据中的 nn 和 kk，我们就只需要求出 1∼n1\sim n 价格的可选礼物总数，和 1∼k1\sim k 价格可选礼物总数，再相减即可得出答案。那么就是二分查找找出 ansans 数组中第一个大于 kk 的元素的下标 firstfirst，以及 ansans 数组中第一个大于 nn 的元素下标 secondsecond。
最后的答案是 second−1second-1 和 second−firstsecond-first。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[10000005];
int asd[10000005],tot;
vector<int> prime;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	vis[0]=vis[1]=1;
	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 i=0;i<prime.size();i++)asd[++tot]=prime[i]*prime[i];
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int n,k;
		cin>>n>>k;
		int down=upper_bound(asd+1,asd+tot+1,k)-asd;
		int up=upper_bound(asd+1,asd+tot+1,n)-asd;
		cout<<max(up-1,0ll)<<" "<<max(up-down,0ll)<<"\n";
	}
	return 0;
}

评论

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

正在加载评论...