题解：SP31040 NGIRL - Namit In Trouble

Dark_Blue_Sky · 2025-05-10 16:16:53 · 题解

题解：SP31040 NGIRL - Namit In Trouble

思路分析

首先，我们理解一下，什么是“恰好拥有 3 个因数”，其中，因为 1\le N\le 10^{10}，所以必定会有两个因数 1 和它本身。那么显而易见了，剩下一个必定是质数。假设这个数是 n，那么它可以分解为 a\times b，其中 2\le a,b\le n，要满足这个条件，只可能 a=b。所以，这个数是一个质数的平方。

那么，我们用筛法筛出 1 \sim 10^6 所有的质数，再枚举筛出来的质数，并将这些质数的平方压入一个数组 ans 中（从小到大压）。

对于每组测试数据中的 n 和 k，我们就只需要求出 1\sim n 价格的可选礼物总数，和 1\sim k 价格可选礼物总数，再相减即可得出答案。那么就是二分查找找出 ans 数组中第一个大于 k 的元素的下标 first，以及 ans 数组中第一个大于 n 的元素下标 second。

最后的答案是 second-1 和 second-first。

代码

#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;
}