CF920G List Of Integers

我们将 $L(x,p)$ 定义为：所有满足 $gcd(p, y) = 1$ 并且 $y > x$ 的整数 $y$ 组成的升序无限整数序列（其中 $\gcd$ 表示两数的最大公约数）。$L(x,p)$ 的元素以 $1$ 为下标。例如，$9$、$13$ 和 $15$ 分别是 $L(7,22)$ 的第 $1$、第 $2$ 和第 $3$ 个元素。 你需要处理 $t$ 组查询。每组查询包含三个整数 $x$、$p$ 和 $k$，你需要输出 $L(x,p)$ 的第 $k$ 个元素。

第一行包含一个整数 $t$（$1 \leq t \leq 30000$），表示需要处理的查询数。 接下来的 $t$ 行，每行包含三个整数 $x$、$p$ 和 $k$，表示第 $i$ 个查询（$1 \leq x, p, k \leq 10^{6}$）。

输出 $t$ 个整数，第 $i$ 个整数为第 $i$ 个查询的答案。

由 ChatGPT 5 翻译