HDU5943 Kingdom of Obsession 暴力判质数+二分匹配

http://acm.hdu.edu.cn/showproblem.php?pid=5943


Kingdom of Obsession

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are $n$ people with their id continuous $(s+1, s+2, \cdots, s+n)$ standing in a line in arbitrary order, be more obsessively, people with id $x$ wants to stand at $y^{th}$ position which satisfy
$$x \mod y = 0$$
Is there any way to satisfy everyone's requirement?

Input

First line contains an integer $T$, which indicates the number of test cases.
Every test case contains one line with two integers $n$, $s$.
Limits
$1 \leq T \leq 100$.
$1 \leq n \leq 10^9$.
$0 \leq s \leq 10^9$.

Output

For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.

Sample Input

2
5 14
4 11

Sample Output

Case #1: No
Case #2: Yes

Source

 

题意:

有n个人,分别id为s+1,s+2,……s+n,现在让这n个人排队,要求每个位置的人的id要能被位置号整除,问是否可行。

思路:

考虑到id为质数的人,只能被放到第一个位置,或者放到位置号和他id相同的位置。当s+1……s+n区间内出现2个质数以上质数的时候,一定要将后部分放到前面去。因为数据范围为$1 \leq n \leq 10^9$.$0 \leq s \leq 10^9$.这个范围下相邻的两个质数都靠的比较近,可以暴力从s+n开始往前,验证区间的质数是否大于等于2。

如果区间内的质数小于2个,则将s+1到s+n的数与1到n进行二分匹配。

如果区间内的质数大于等于2个,则将后s个数与1到s进行二分匹配。

如果完全匹配上就是可行的。