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

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;

}

秒客网