P5535 【XR-3】小道消息

题目描述

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

有 n 个人，其中第 i 个人的衣服上有一个数 i+1。小 X 发现了一个规律：当一个衣服上的数为 i 的人在某一天知道了一条信息，他会在第二天把这条信息告诉衣服上的数为 j 的人，其中 gcd(i,j)=1（即 i,j 的最大公约数为 1）。在第 0 天，小 X 把一条小道消息告诉了第 k 个人，小 X 想知道第几天时所有人都会知道这条小道消息。

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

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

输入格式

一行 2 个正整数 n,k。

数据范围：

• 2 ≤ n ≤ 1e14。
• 1 ≤ k ≤ n。

输出格式

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

输入输出样例

输入 #1

3 1

输出 #1

2

输入 #2

6 4

输出 #2

1

题解：

观察 数据范围 可知暴力摸你是完全不可能的

根据出题人的良心提示 ：伯特兰-切比雪夫定理。--（对于所有大于3的整数n，存在一个质数p，符合 n < p < 2*n - 2 ;

对一个质数而言，若存在另一个数 与它不互质，那这个数一定是这个质数的倍数

即：假定这个质数为 x，则在区间[2 ,2*x - 1]中，除了它自己本身，所有的数与它互质

也就是 gcd(i ,x) = 1,  (2 <= i <= 2*x-1，i != x)

例如：质数43 在区间[2 ,2 * 43 - 1]中，除了43 所有数与它互质，质数7 在区间[2 ,2 * 7 - 1]中同样

情况一： 如果(k+1)为质数  则在区间[2 ,2*k ]中，全部与它互质，若n <= 2*k 那么第一天所有人都知道消息，输出\"1\"；

情况二：如果(k+1)不为质数，那第一天它可以传给尽量大的接近 n 的质数，如此就变成了情况一，在情况一的基础上多加一天，即输出\"2\"；

#include#include#include#include#include#include#include#include#include#include#include#include