题目描述

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

输入格式

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

输出格式

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

1 2

2

2 3

9

1000 1000003

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$。