题解：AT_abc300_g [ABC300G] P-smooth number

观察到

100

以内的质数只有

25

个，这是一个很好的折半搜索的数据范围。

考虑一个中间值

B

，搜出

\le B

的所有情况和

>B

的所有情况，枚举一下拼起来即可。

这里只用选取一个合适的

B

就可以了。打个搜索出来看一下数据规模，发现取

B=8

非常优秀，开销在对

>B

部分的排序以及二分，时间复杂度理论

\Theta((\pi(n) - B)^{\log n} \log n \log B)

，事实上远远跑不满，因为指数上可取的值越来越少。

时间仅用 500ms，是时限的

\frac{1}{8}

。

CPP

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define db double
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f,mod=1e9+7;
const long long INFL=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
il int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
il void chkmax(int &x,int y){x=(x<y)?y:x;}
il void chkmin(int &x,int y){x=(x>y)?y:x;}

const int N=105;
int np[N],prime[N],cnt;
int n,p;
void init(int n){
    np[1]=1;
    rep(i,2,n){
        if(!np[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
            np[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int mid;
vint res1,res2;
void dfs(int k,int lim,int num,vint &res){
    // cout<<k<<" "<<num<<endl;
    if(k==lim+1){
        res.push_back(num);return;
    }
    dfs(k+1,lim,num,res);
    while(1){
        if(num*prime[k]>n) break;
        num*=prime[k];
        dfs(k+1,lim,num,res);
    }
}
signed main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n>>p;
    init(p);
    mid=min(8ll,cnt);
    res1.reserve(3197529),res2.reserve(2812349);
    dfs(1,mid,1,res1);
    dfs(mid+1,cnt,1,res2);
    sort(all(res1)),sort(all(res2));
    int ans=0;
    
    // cout<<ans<<endl;
    cerr<<res1.size()<<" "<<res2.size()<<endl;
    for(auto i:res1){
        int tar=n/i;
        auto it=upper_bound(all(res2),tar);
        if(it==res2.begin()) continue;
        --it;
        ans+=it-res2.begin()+1;
    }
    cout<<ans<<endl;
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

题解：AT_abc300_g [ABC300G] P-smooth number

文章操作

相关推荐

评论

题解：AT_abc300_g [ABC300G] P-smooth number