#P5535. 【XR-3】小道消息

    ID: 4839 远端评测题 1000ms 250MiB 尝试: 2 已通过: 2 难度: 10 上传者: 标签>数学O2优化素数判断,质数,筛法最大公约数,gcd

【XR-3】小道消息

题目描述

小 X 想探究小道消息传播的速度有多快,于是他做了一个社会实验。

nn 个人,其中第 ii 个人的衣服上有一个数 i+1i+1。小 X 发现了一个规律:当一个衣服上的数为 ii 的人在某一天知道了一条信息,他会在第二天把这条信息告诉衣服上的数为 jj 的人,其中 gcd(i,j)=1\gcd(i,j)=1(即 i,ji,j 的最大公约数为 11)。在第 00 天,小 X 把一条小道消息告诉了第 kk 个人,小 X 想知道第几天时所有人都会知道这条小道消息。

可以证明,一定存在所有人都知道了这条小道消息的那一天。

提示:你可能需要用到的定理——伯特兰-切比雪夫定理

输入格式

一行 22 个正整数 n,kn,k

数据范围:

  • 2n10142 \le n \le 10^{14}
  • 1kn1 \le k \le n

输出格式

一行一个正整数,表示答案。

3 1

2

6 4

1

提示

【样例 11 说明】

33 个人的衣服上的数分别为 2 3 4

在第 00 天,小 X 把一条小道消息告诉了第 11 个人,他的衣服上的数为2。

在第 11 天,第 11 个人会告诉第 22 个人,因为 gcd(2,3)=1\gcd(2,3) = 1,但他不会告诉第 33 个人,因为 gcd(2,4)=21\gcd(2,4) = 2 \ne 1

在第 22 天,第 22 个人会告诉第 33 个人,因为 gcd(3,4)=1\gcd(3,4) = 1,这时所有人都知道了这条小道消息,因此答案为 22