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<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<unordered_set>
#include<set>
#include<map>
#include<bitset>
#define inf 1000000000
#define int long long
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 200086;int n, k;
int a[N];bool prim(int x) {if (x == 1) return 0;if (x == 2) return 1;if (x % 2 == 0) return 0;for (int i = 3; i <= sqrt(x); i += 2) {if (x % i == 0) return 0;}return 1;
}void solve() {cin >> n >> k;if (prim(k + 1) && 2 * k >= n) cout << 1 << endl;else cout << 2 << endl;}signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T = 1;//cin >> T;while (T--) solve();return 0;
}