賽后題解——真偽亞瑟王

C. 真偽亞瑟王
題目描述

魔術師梅林在水晶球中預見了莫德雷德的叛逆，她決定在在莫德雷德叛逆之前采取一個有效的策略保護亞瑟王，
具體做法如下：使用魔法將亞瑟王復制成N份，當然，其中只有一個使真的，她認為這樣就能有效的保護亞瑟王不被殺死，
為了自己能最終找到亞瑟王，她將所有的亞瑟王按1-N編號，并設定了一個密碼數字X，真亞瑟王的編號是最接近N的且不能被2?X中任何一個數整除的數，（即真亞瑟王的編號的約數不再2?X中），

輸入

兩個整數X,N，用一個空格隔開，

輸出

真亞瑟王的編號，

樣例輸入

3 6

樣例輸出

5

樣例輸入

3 4

樣例輸出

1

樣例輸入

5 50

樣例輸出

49

提示

【資料范圍】
對于30%的資料， 2 ≤ X ≤ N ≤ 10 2≤X≤N≤10 2≤X≤N≤10
對于60%的資料， 2 ≤ X ≤ N ≤ 1000 2≤X≤N≤1000 2≤X≤N≤1000
對于80%的資料， 2 ≤ X ≤ N ≤ 1 0 5 2≤X≤N≤10^5 2≤X≤N≤105
對于100%的資料， 2 ≤ X ≤ N ≤ 1 0 9 2≤X≤N≤10^9 2≤X≤N≤109

解決思路：分類討論

提示：不合法代表一定不是答案，合法代表一定是答案，
已知：對于整數 n n n，小于等于 n n n且距離最近的素數離 n n n不會太遠，所以直接暴力列舉，判斷素數即可，
第一類： x 2 ≥ n x^2 \ge n x2≥n
1、因為一個合數肯定有一個小于等于根號的因子，所以小于等于 n n n的所有合數的最小因子必然在區間 [ 2 , x ] [2,x] [2,x]內，因此[ 2 , n ] 2,n] 2,n]的合數不合法，
2、 [ 2 , x ] [2,x] [2,x]的每個數不合法，
綜上所述， [ x + 1 , n ] [x+1,n] [x+1,n]的素數可能合法，
暴力判斷小于等于 n n n且距離最近的素數（前提是大于等于 x + 1 x+1 x+1或者大于 x x x）
若存在素數，輸出素數，
若不存在素數，輸出 1 1 1（由于 [ 2 , n ] [2,n] [2,n]中沒有一個數合法，只剩下數字 1 1 1了）
第二類： x 2 < n x^2 < n x2<n
1、因為一個合數肯定有一個小于等于根號的因子，所以小于等于 x 2 x^2 x2的所有合數的最小因子必然在區間 [ 2 , x ] [2,x] [2,x]內，因此 [ 2 , x 2 ] [2,x^2] [2,x2]的合數不合法，但是 [ x 2 + 1 , n ] [x^2+1,n] [x2+1,n]的合數可能合法，
例如： x = 2 ， n = 99 x=2，n=99 x=2，n=99時， 99 99 99合法但是是合數，
2、 [ x + 1 , n ] [x+1,n] [x+1,n]的素數可能合法，
綜上所述，從 n n n開始往小于 n n n的數開始判斷，如果這個數是素數或者它不是 [ 2 , x ] [2,x] [2,x]中任意數的倍數的話，輸出這個數即可（直接列舉小于根號的因子判斷是否在 [ 2 , x ] [2,x] [2,x]內）

#include<cmath>
#include<queue>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define mod 77797
typedef long long ll;
const int N = 2e1 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

bool judge(int n, int x) {
	if (n == 1) return true;
	if (n >= 2 && n <= x) return false;

	for (int i = 2; i <= n / i; i++) {
		if (n % i == 0) {
			if (i <= x) return false;
		}
	}
	return true;
}
bool isPrime(ll n) {
	if (n == 1) return false;
	for (int i = 2; i <= n / i; i++) {
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

int main() {

	ll x, n;
	cin >> x >> n;

	if (x * x >= n) {
		while (n > x) {
			if (isPrime(n)) {
				cout << n << endl;
				return 0;
			}
			n--;
		}
		cout << 1 << endl;
		return 0;
	}
	else {
		while (n) {
			if (judge(n, x)) {
				cout << n << endl;
				return 0;
			}
			n--;
		}
	}
	return 0;
}