1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 using namespace std; 7 int n,p,top,list[105],bin[18],num[200005],ans,l,r,mid; 8 bool bo[15000005],vis[105]; 9 int lowbit(int x){
    return x&(-x);}10 int work(int x,int y){11     long long fuckpps=1;12     for (int i=1;i<=top;i++){13         if (x&bin[i-1]) fuckpps=fuckpps*list[i];14         if (fuckpps>1e9) return 0;15     }16     return y/fuckpps*(num[x]%2==0?1:-1);17 }18 bool check(int x){19     x/=p;20     int sum=0;21     for (int i=0;i
           
            =n;23 }24 int main(){25 int x;26 cin>>n>>p;27 if (p>=69){28 x=1000000000/p;29 memset(bo,1,sizeof(bo)); bo[1]=1; int cnt=1;30 if (n==1){31 printf("%d\n",p);32 return 0;33 }34 for (int i=2;i<=x;i++){35 if (bo[i]){36 if (i
            
             =p) break;52 vis[i*list[j]]=1;53 if (i%list[j]==0) break; 54 }55 }56 bin[0]=1; for (int i=1;i<=top;i++) bin[i]=bin[i-1]<<1;57 for (int i=1;i
             
              >1;61 if (check(mid)) ans=mid,r=mid-1;62 else l=mid+1;63 }64 printf("%d\n",ans);65 return 0;66 }
             
            
           
          
         
        
       
      

链接：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)）。