題目描述

小 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;
}