题解：SP8238 NFACTOR - N-Factorful

Dark_Blue_Sky · 2025-05-10 14:08:46 · 题解

题解：SP8238 NFACTOR - N-Factorful

思路分析

我们先用筛法筛出 1 \sim 10^6 所有的质数。

然后，我们再枚举 1\sim 10^6 中的所有整数 i，并用根号级（枚举 1\sim \sqrt{n} 中所有的素数）的时间算出 i 的因子个数 s，并标记 sum_{i,s} 为 1。

接着，我们对 sum_i 进行前缀和即可求出 sum_{i,1 \sim n} 的答案。

最后输入时，只需要输出 sum_{r,n}-sum_{l-1,n} 即可。

代码

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