[原创]HDU 5943 Kingdom of Obsession [素数间隔+二分图匹配]【数论+图论】

2017-01-26 21:31:23 Tabris_ 阅读数：194

博客爬取于2020-06-14 22:41:56
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54746352

题目连接：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)
Total Submission(s): 789 Accepted Submission(s): 215

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,⋯,s+n) standing in a line in arbitrary order, be more obsessively, people with id x wants to stand at yth position which satisfy

xmody=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≤T≤100.
1≤n≤109.
0≤s≤109.

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个人分别标号为{S+1,S+2,,,,S+N}\{S+1,S+2,,,,S+N\}现在要在[1,N][1,N]这些位置上按照下列要求给这N个人串个座位,使得每个人的座位号整除标号.问你有没有可行方案.

解题思路:
很明显,{S+1,S+2,,,,S+N}\{S+1,S+2,,,,S+N\}区间中只能有一个素数,要坐在1的位置上,其余地方都不行.
然后查了一下素数间隔,最大的素数间隔只有777.那么就是N>777的时候都是NO,
这样的话就可以大数据直接NO,小数据在考虑了,

特别考虑的就是当S< N的时候{S+1,S+2,,,,N}\{S+1,S+2,,,,N\}可以直接放到本位置，那么只需要考虑{N+1,N+2,,,,S+N}\{N+1,N+2,,,,S+N\}这些数就好了，将S，N互换一下即可。

每个标号能做的位置是固定的,那么将人和位置分开就是一个二分图了,接着对二分图进行完美匹配就好了.

附本题代码
--------------------------------------------------------------------------------------.

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
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    N   = 1000000+7;
const int    MOD = 1e9+7;
const double eps = 1e-6;
const double PI  = acos(-1.0);

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void fre(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
inline int gcd(int a,int b){return (b==0)?a:gcd(b,a%b);}
/***********************************************************************/
int match[2000];
int vis[2000];
vector<int >mmp[2000];

int find(int u){
    for(int i=0;i<mmp[u].size();i++){
        int v=mmp[u][i];
        if(vis[v]==0){
            vis[v]=1;
            if(match[v]==-1||find(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

bool prime(int x){
    if(x==0||x==1)return false;
    if(x==2) return true;
    if(x%2==0) return false;
    for(int i=3;i*i<=x;i+=2)
        if(x%i==0) return false;
    return true;
}

int main(){
    int _,kcase;
    while(~s1(_)){
        kcase = 0;
        while(_--){

            int n,s;
            s1(n),s1(s);
            printf("Case #%d: ",++kcase);
            if(s<n) s^=n,n^=s,s^=n;
            if(n>777) puts("No");
            else {
                int num = 0;
                for(int i=1;i<=n&&num<=2;i++)
                    if(prime(s+i)) num++;
                if(num>1) {puts("No");continue; }


                memset(match,-1,sizeof(match));
                for(int i=1;i<=n+n;i++) mmp[i].clear();

                for(int i=1;i<=n;i++)
                    for(int j=1;j<=n;j++)
                        if((s+i)%j==0) mmp[i].pb(j+n),mmp[j+n].pb(i);

                int ans = 0;
                for(int i=1;i<=n;i++){
                    memset(vis,0,sizeof(vis));
                    if(find(i)) ans++;
                }

                if(ans==n) puts("Yes");
                else    puts("No");
            }
        }
    }

    return 0;
}