题目
题目描述
小 X 想探究小道消息传播的速度有多快，于是他做了一个社会实验。
有 n 个人，其中第 i 个人的衣服上有一个数 i+1。小 X 发现了一个规律：当一个衣服上的数为 i 的人在某一天知道了一条信息，他会在第二天把这条信息告诉衣服上的数为 j 的人，其中 gcd(i,j)=1（即 i,j的最大公约数为 1）。在第 0 天，小 X 把一条小道消息告诉了第 k 个人，小 X 想知道第几天时所有人都会知道这条小道消息。
可以证明，一定存在所有人都知道了这条小道消息的那一天。
提示：你可能需要用到的定理——伯特兰-切比雪夫定理。
输入格式
一行 2 个正整数 n,k。
数据范围：
2≤n≤10^14
1≤k≤n。
输出格式
一行一个正整数，表示答案。
输入输出样例
输入 #1
3 1
输出 #1
2
输入 #2
6 4
输出 #2
1
分析
第i个人身上的数是i+1,i最小是1，所以k+1最小是2
告诉第k个人，他身上的数是k+1,以下对k+1操作
伯特兰-切比雪夫定理
若整数n > 3，则至少存在一个质数p，符合n < p < 2n − 2。另一个稍弱说法是：对于所有大于1的整数n，存在一个质数p，符合n < p < 2n
这里使用第一条
对k+１分类讨论，
1.若k＋１是个质数
1）若(n/2 < k+1 <= n),那么就算是k＋１的２倍，也比ｎ大，所以在［１，ｎ］里没有ｋ＋１的倍数。则只需要一天，ｋ＋１就能把消息告诉所有人
２）若(k+1<=n/2),那么k+1的二倍在[1,n]里，在[1,n]里有k+1的倍数。ｋ+1需要一天把消息告诉所有不是它倍数的数，并且没有两个k+1的倍数是相邻的，所以在第二天k+1的倍数两边相邻的数可以把消息告诉他们，总共需要两天
2.若k+1是个合数
k+1肯定不是2，也不是3，那么k+1 > 3,满足伯特兰-切比雪夫定理的要求
根据定理，必有一素数p，满足([/frac{n}{2}] < p < n)（n>=2）,而p与任何不是它倍数的数互质。这里p的2倍已经大于n了，所以[1,n]里没有p的倍数,所以p和k+1互质，那么k+1花一天告诉p，转化为第一种情况，p再用一天告诉所有人，总共两天。
对p讨论完毕，答案只可能是1或2
代码实现
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define F(a,b,c) for(int a = b; a <= c; a++)
#define UF(a,b,c) for(int a = b; a >= c; a--)
using namespace std;
typedef long long ll;
ll n, k;
bool prime(ll k){//判断质数
for(ll i = 2; i <= sqrt(k); i++){
if(k % i == 0) return 0;
}
return 1;
}
int main(){
cin >> n >> k;
n++;
k++;
if(prime(k) && k > n / 2){//第一种情况
cout << 1 << endl;
return 0;
}
if(prime(k)){//第二种情况
cout << 2 << endl;
return 0;
}
else{//第三种情况
cout << 2 << endl;
}
return 0;
}
有错请指出！