记录编号	141110	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[COCI 2011] BROJ	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2014-11-29 10:54:11	内存使用	1.87 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
using namespace std;
typedef long long LL;
const int C=71;
const LL SUP=1000000000;
int checkprime(int p){
	for(int i=2;i<p;i++) if(p%i==0) return false;
	return true;
}
int N,P;
LL mx;
int cnt;
vector<int> prime;
void DFS(LL now,int k,int sgn){
	if(k==prime.size()){
		cnt+=(mx/now)*sgn;
		return;
	}
	if(now*prime[k]<=mx) DFS(now*prime[k],k+1,-sgn);
	DFS(now,k+1,sgn);
}
void work_small(void){
	for(int i=2;i<P;i++){
		if(checkprime(i)) prime.push_back(i);
	}
	LL l=1,r=SUP/P+1;
	while(l<r){
		LL mid=(l+r)>>1;
		cnt=0,mx=mid;
		DFS(1,0,1);
		//cnt=最小素因子为P的个数
		if(cnt<N) l=mid+1;
		else r=mid;
	}
	LL ans=l*P;
	if(ans>SUP) ans=0;
	printf("%lld\n",ans);
}
bitset<13000000> flag;
void work_large(void){
	LL mx=SUP/P;
	cnt=1;
	if(cnt==N){
		printf("%d\n",P);
		return;
	}
	for(LL i=2;i<=mx;i++){
		if(!flag[i]){
			if(i<P){
				for(LL j=i*i;j<=mx;j+=i) flag[j]=true;
			}
			else{
				cnt++;
				if(cnt==N){
					printf("%lld\n",i*P);
					return;
				}
			}
		}
	}
	printf("0\n");
}
int main(){
	freopen("broj.in","r",stdin);
	freopen("broj.out","w",stdout);
	scanf("%d%d",&N,&P);
	if(P<=73) work_small();
	else work_large();
	return 0;
}