#P10849. [POI2021 R2]Liczby względnie pierwsze

    ID: 9974 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-试除法分解质因数全子集枚举容斥原理二分第 k 小

[POI2021 R2]Liczby względnie pierwsze

题目描述

定义 aa 的「不友好数」bb 为 gcd⁡(a,b)=1\gcd(a,b)=1 的数。

现在你知道了数字 nn,你需要求出它的「不友好数」升序排序第 kk 个开始后的 cc 个数。

输入格式

一行,三个数 $n,k,c\ (2 \leq n \leq 10^{14}, 1 \leq k \leq 10^{14}, 1 \leq c \leq 10^5)$。

输出格式

输出 cc 个数,表示第 k∼k+c−1k \sim k+c-1 个 nn 的「不友好数」。

输入输出样例 #1

输入 #1

10 3 4

输出 #1

7 9 11 13

说明/提示

样例解释:

1010 的「不友好数」依次为 1,3,7,9,11,13,17…1,3,7,9,11,13,17\ldots。

子任务分配如下:

子任务编号 特殊性质 分值
11 n≤106n \leq 10^6 且 M≤nM \leq n 1010
22 f(n)≤106f(n) \leq 10^6 且 M≤nM \leq n 3636
33 c≤100c \leq 100 3030
44 无特殊限制 2424

上述 MM 为输出的最大值,f(n)f(n) 为 ≤n\leq n 的「不友好数」数量。