#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n,p,top,list[],bin[],num[],ans,l,r,mid;
bool bo[],vis[];
int lowbit(int x){return x&(-x);}
int work(int x,int y){
long long fuckpps=;
for (int i=;i<=top;i++){
if (x&bin[i-]) fuckpps=fuckpps*list[i];
if (fuckpps>1e9) return ;
}
return y/fuckpps*(num[x]%==?:-);
}
bool check(int x){
x/=p;
int sum=;
for (int i=;i<bin[top];i++){sum+=work(i,x);}
return sum>=n;
}
int main(){
int x;
cin>>n>>p;
if (p>=){
x=/p;
memset(bo,,sizeof(bo)); bo[]=; int cnt=;
if (n==){
printf("%d\n",p);
return ;
}
for (int i=;i<=x;i++){
if (bo[i]){
if (i<p) for (long long j=1LL*i*i;j<=x;j+=i) bo[j]=;
else{
cnt++; if (cnt==n){printf("%d\n",i*p);return ;}
}
}
}
if (cnt<n) puts("");
return ;
}
top=; memset(vis,,sizeof(vis));
for (int i=;i<p;i++){
if (!vis[i]){
list[++top]=i;
}
for (int j=;j<=top;j++){
if (i*list[j]>=p) break;
vis[i*list[j]]=;
if (i%list[j]==) break;
}
}
bin[]=; for (int i=;i<=top;i++) bin[i]=bin[i-]<<;
for (int i=;i<bin[top];i++) num[i]=num[i-lowbit(i)]+;
ans=; l=,r=1e9;
while (l<=r){
mid=(l+r)>>;
if (check(mid)) ans=mid,r=mid-;
else l=mid+;
}
printf("%d\n",ans);
return ;
}
链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3181
题意:求最小质因子等于p的第n小的正整数(恰好有n-1个最小质因子等于p且比它
小的正整数)。p一定是质数。若答案超过10^9则输出0。
做法:当p>=69时,10^9/p可以接受线性算法,我们就找到1~10^9/p中最小质因子>=p的个数,我们可以用筛法实现,具体见代码,比较神奇。
当p<=61时,我们考虑二分答案x,然后容斥即可,复杂度为O(min(10^9/p,2^(小于p的质数个数)LogL))。