P8084 [COCI 2011/2012 #4] BROJ

题目描述

求最小质因数为 $P$ 的不超过 $10^9$ 的第 $N$ 小正整数。

输入格式

第一行，两个整数 $N,P$。保证 $P$ 为质数。

输出格式

输出所求的不超过 $10^9$ 的第 $N$ 小正整数。如果答案超过 $10^9$，则输出 $0$。

输入输出样例 #1

输入 #1

1 2

输出 #1

2

输入输出样例 #2

输入 #2

2 3

输出 #2

9

输入输出样例 #3

输入 #3

1000 1000003

输出 #3

0

说明/提示

【数据规模与约定】

• 对于 $30\%$ 的数据，输出小于 $10^5$（含 $0$）。
• 对于另外 $30\%$ 的数据，$P \gt 1000$。
• 对于 $100\%$ 的数据，$1 \le N,P \le 10^9$。

【提示与说明】

题目译自 COCI 2011-2012 CONTEST #4 Task 5 BROJ。

本题分值按 COCI 原题设置，满分 $140$。