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
若i合法，则i%c必然合法。故i=a[k]+t*C (t>0)
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;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<sqrt(MAXN)) {cout<<'0'<=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<MAXN) puts("0");
else cout<
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;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<sqrt(MAXN)) {cout<<'0'<=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<MAXN) puts("0");
else cout<