BZOJ 3181([Coci2012]BROJ-最小質因子為p的第k小素數)

3181: [Coci2012]BROJ
Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 26  Solved: 7
[Submit][Status]
Description
求最小質因子等於p的第n小的正整數（恰好有n-1個最小質因子等於p且比它
小的正整數）。p一定是質數。若答案超過10^9則輸出0。
 

Input
Output
Sample Input
2 3

Sample Output
9
HINT

1 <= n, p <= 10^9

Source

[Submit][Status]


當n≥29時，枚舉p的倍數，暴力可過。

當n<29時：暴力枚舉不可過

開始找規律---發現循環節

設C為≤p的素數之積

經過cwj的證明：

若P<29，可以直接計算，設C為<=P的質數的積，由於P不大，C只是百萬級的，硬統計C內有多少個符合要求，設符合要求的個數為c，則答案為((N-1)/c)*C+a[(N-1)%c+1]，其中a[i]為第i個符合要求的數，現證明其正確性。

  我們認為，若i合法，則C+i合法。

  現反設C+i非法，則存在p<P滿足p|C+i，因為C為<=P的質數的積，所以p|C，所以p|i，與假設矛盾，得證。

若i合法，則i%c必然合法。故i=a[k]+t*C (t>0)

 #include<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
#include<cassert>  
#include<climits>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;i++)  
#define Fork(i,k,n) for(int i=k;i<=n;i++)  
#define ForD(i,n) for(int i=n;i;i--)  
#define Forp(x) for(int p=pre[x];p;p=next[p])  
#define RepD(i,n) for(int i=n;i>=0;i--)  
#define MEM(a) memset(a,0,sizeof(a))  
#define MEMI(a) memset(a,127,sizeof(a))  
#define MEMi(a) memset(a,128,sizeof(a))  
#define INF (2139062143)  
#define F (1000000009)  
#define MAXN (1000000000)  
#define MAXP (5000000)  
typedef long long ll; 
ll n,p; 
int a[300]={0},size=0; 
bool b[300]={0}; 
void make_prime(int n) 
{ 
    size=0; 
    b[1]=1; 
    Fork(i,2,n) 
    { 
        if (!b[i]) a[++size]=i; 
        For(j,size) 
        { 
            if (i*a[j]>n) break; 
            b[i*a[j]]=1; 
            if (i%a[j]==0) break; 
        } 
    } 
} 
int ans[10000000],tot=0; 
int main() 
{ 
//  freopen("bzoj3181.in","r",stdin);  
    while (cin>>n>>p) 
    { 
        if (n==1) {cout<<p<<endl;continue;} 
        if (p>sqrt(MAXN)) {cout<<'0'<<endl;continue;} 
        if (p>=29) 
        { 
            int k=1; 
            for(int i=2*p;i<=MAXN;i+=p) 
            { 
                bool bo=0; 
                Fork(j,2,p-1)  
                    if (i%j==0) {bo=1;break;} 
                if (!bo) k++; 
                if (k==n) {cout<<i<<endl;break;} 
            } 
            if (k<n) puts("0"); 
        } 
        else 
        { 
            make_prime(p);   
            ll C=1; 
            For(i,size) C*=a[i];//,cout<<C<<endl;  
            tot=0; 
            for(ll i=p;i<=C&&i<=MAXN;i+=p)  
            { 
                bool bo=0; 
                For(j,size) 
                { 
                    if (i%a[j]==0&&a[j]<p) {bo=1;break;} 
                } 
                if (!bo) ans[++tot]=i;           
            } 
            //if (n<=tot) cout<<ans[n]<<endl;  
        //  if (tot==0) {puts("0");return 0;}  
            ll ans2=(ll)(n-1)/tot*C+ans[(n-1)%tot+1]; 
            if (ans2>MAXN) puts("0"); 
            else cout<<ans2<<endl; 
        } 
    //  return 0;  
         
    } 
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (1000000000)
#define MAXP (5000000)
typedef long long ll;
ll n,p;
int a[300]={0},size=0;
bool b[300]={0};
void make_prime(int n)
{
 size=0;
 b[1]=1;
 Fork(i,2,n)
 {
  if (!b[i]) a[++size]=i;
  For(j,size)
  {
   if (i*a[j]>n) break;
   b[i*a[j]]=1;
   if (i%a[j]==0) break;
  }
 }
}
int ans[10000000],tot=0;
int main()
{
// freopen("bzoj3181.in","r",stdin);
 while (cin>>n>>p)
 {
  if (n==1) {cout<<p<<endl;continue;}
  if (p>sqrt(MAXN)) {cout<<'0'<<endl;continue;}
  if (p>=29)
  {
   int k=1;
   for(int i=2*p;i<=MAXN;i+=p)
   {
    bool bo=0;
    Fork(j,2,p-1)
     if (i%j==0) {bo=1;break;}
    if (!bo) k++;
    if (k==n) {cout<<i<<endl;break;}
   }
   if (k<n) puts("0");
  }
  else
  {
   make_prime(p); 
   ll C=1;
   For(i,size) C*=a[i];//,cout<<C<<endl;
   tot=0;
   for(ll i=p;i<=C&&i<=MAXN;i+=p)
   {
    bool bo=0;
    For(j,size)
    {
     if (i%a[j]==0&&a[j]<p) {bo=1;break;}
    }
    if (!bo) ans[++tot]=i;   
   }
   //if (n<=tot) cout<<ans[n]<<endl;
  // if (tot==0) {puts("0");return 0;}
   ll ans2=(ll)(n-1)/tot*C+ans[(n-1)%tot+1];
   if (ans2>MAXN) puts("0");
   else cout<<ans2<<endl;
  }
 // return 0;
  
 }
 return 0;
}