AdditionalFile4851.zip

#4851. 「POI 2021/2022 R2」Liczby względnie pierwsze

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Liczby względnie pierwsze

最近，Bajtazar 迷上了互质数的研究。所谓自然数 $x$ 与自然数 $y$ 互质，是指它们的最大公约数为 $1$。例如，与 $10$ 互质的数字包括：

Bajtazar 将所有与数字 $n$ 互质的数字按升序写了出来，把这个列表装裱起来，从此称之为「Bajtazar 列表」。

在将这份作品挂上墙前，他想先检查一下列表的正确性。由于这个列表是无穷长的，他决定只抽查其中一段长度为 $c$ 的片段，从第 $k$ 个位置开始。列表中的元素从 $1$ 开始依次编号。你愿意帮助他完成这个任务吗？

输入格式

输入的第一行包含三个自然数 $n, k, c$ $(2 \leq n \leq 10^{14}, 1 \leq k \leq 10^{14}, 1 \leq c \leq 100000)$，分别表示 Bajtazar 选定的数字、检查片段的起始位置以及片段的长度。

输出格式

你的程序应输出一行，包含 $c$ 个自然数，用单个空格分隔，表示 Bajtazar 列表中第 $k, (k+1), (k+2), \ldots, (k+c-1)$ 个位置上的元素。提醒一下，这个列表包含所有与 $n$ 互质的数字，按升序排列。

样例 1

输入

10 3 4

输出

7 9 11 13

Bajtazar 询问列表中第 $3, 4, 5,6$ 个位置的元素。对于 $n=10$，Bajtazar 列表依次为 $1, 3, 7, 9, 11, 13, 17, \ldots$。

样例 2

见附加文件下 [lic1.in](file:lic1.in) 和 [lic1.out](file:lic1.out)。

该样例满足 $n=2^{15}, k=1000, c=15300$；

样例 3

见附加文件下 [lic2.in](file:lic2.in) 和 [lic2.out](file:lic2.out)。

该样例满足 $n=257040, k=100, c=100$；

样例 4

见附加文件下 [lic3.in](file:lic3.in) 和 [lic3.out](file:lic3.out)。

该样例满足 $n, k$ 在 $[10^{13}, 10^{14}]$ 范围内随机，$c=100$；

样例 5

见附加文件下 [lic4.in](file:lic4.in) 和 [lic4.out](file:lic4.out)。

该样例满足 $n, k$ 在 $[10^{13}, 10^{14}]$ 范围内随机，$c=100000$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

其中，$M$ 表示输出中最后一个数字，$f(n)$ 表示不超过 $n$ 且与 $n$ 不互质的数字个数。