分类：二分匹配

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

2016年中国大学生程序设计竞赛（杭州）
 

题意：

有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进行二分匹配。

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL maxn = 2510;
const LL maxm = 1000010;
LL cnt, p[maxn];
struct node
{
    LL v, next;
} E[maxm];
LL n, m;
void init()
{
    cnt = 0;
    memset(p, -1, sizeof(p));
}
void add(LL u, LL v)
{
    E[cnt].v = v;
    E[cnt].next = p[u];
    p[u] = cnt++;
}
LL fg[maxn];
LL pp[maxn];
bool Find(LL x)
{
    for (LL i = p[x]; i != -1; i = E[i].next)
    {
        LL y = E[i].v;
        if (!fg[y])
        {
            fg[y] = 1;
            if (pp[y] == 0 || Find(pp[y]))
            {
                pp[y] = x;
                return 1;
            }
        }
    }
    return 0;
}
LL solve()
{
    LL ans = 0;
    for (LL i = 1; i <= n; i++) pp[i] = 0;
    for (LL i = 1; i <= n; i++)
    {
        for (LL j = 1; j <= n; j++) fg[j] = 0;
        if (Find(i)) ans++;
    }
    return ans;
}
 
bool isprime(LL x)
{
    for (LL i = 2; i * i <= x; i++)
        if (x % i == 0) return 0;
    return 1;
}
int main()
{
    LL T, ks = 0;
    scanf("%lld", &T);
    while (T--)
    {
        init();
        LL N;
        LL x, y;
        scanf("%lld %lld", &y, &x);
        printf("Case #%lld: ", ++ks);
        N = y;
        y += x;
        x++;
        LL cntx = 0;
        LL p1, p2;
        for (LL i = y; i >= x; i--)
        {
            if (isprime(i))
            {
                cntx++;
                if (cntx == 1)
                    p2 = i;
                else
                {
                    p1 = i;
                    break;
                }
            }
        }
        if (cntx <= 1)
        {
            for (LL i = x; i <= y; i++)
            {
                for (LL j = 1; j * j <= i && j <= N; j++)
                    if (i % j == 0)
                    {
                        add(i - x + 1, j);
                        if (i / j <= N && j * j != i)
                            add(i - x + 1, i / j);
                    }
            }
            n = N;
            LL ans = solve();
            if (ans == n) puts("Yes");
            else puts("No");
        }
        else
        {
            LL need = x - 1;
            if (y - p1 < need)
            {
                puts("No");
                continue;
            }
            LL st = y - need + 1;
            for (LL i = st; i <= y; i++)
            {
                for (LL j = 1; j * j <= i && j <= need; j++)
                    if (i % j == 0)
                    {
                        add(i - st + 1, j);
                        if (i / j <= need && j * j != i)
                            add(i - st + 1, i / j);
                    }
            }
            n = need;
            LL ans = solve();
            if (ans == n) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}