链接：http://acm.hdu.edu.cn/showproblem.php?pid=5943
题意：给定 s，n，判断 s+1，s+2，...，s+n 这 n 个数能否放到 1，2，3，...，n 的位置上（如果 x 可以放到 y 上，则必须满足 x mod y=0 ）
分析：这题是一道很明显的二分图匹配，但是因为 n 是1E9的大小，所以我们没法直接做。但是我们发现如果 [s+1，s+n] 内如果有2个素数，那么肯定不满足（素数只能放在位置1上，2个素数就肯定会冲突），所以我们可以利用这个来缩小 n 的范围，猜测这个距离为1000（实际为500左右？），那么我们用处理的n的范围就大大缩小了。
AC代码：
/************************************************************************* > File Name: K.cpp > Author: Akira > Mail: qaq.febr2.qaq@gmail.com > Created Time: 2017年05月05日 星期五 21时08分56秒 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<algorithm> #include<queue> #include<stack> #include<map> #include<cmath> #include<vector> #include<set> #include<list> #include<ctime> typedef long long LL; typedef unsigned long long ULL; typedef long double LD; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define Sqr(a) ((a)*(a)) using namespace std; #define MaxN 2000 #define MaxM MaxN*20 #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 const int mod = 1e9+7; const int eps = 1e-8; #define bug cout << 88888888 << endl; int T; int n,s,x; struct Edge { int u, v, next; }edge[MaxM]; int cont, head[MaxN]; void add(int u, int v) { edge[cont].v = v; edge[cont].next = head[u]; head[u] = cont++; } void init() { cont = 0; MST(head, -1); } int match[MaxN]; bool check[MaxN]; bool DFS(int u) { for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; if(!check[v]) { check[v] = true; if(match[v]==-1 || DFS(match[v])) { match[v] = u; match[u]= v; return true; } } } return false; } int Hungarian() { int ans = 0; MST(match, -1); for(int i=1;i<=x;i++) { if(match[i] == -1) { CLR(check); if(DFS(i)) ans++; } } //for(int i=1;i<=n;i++) cout << i << " - " << match[i] << endl; return ans; } int main() { scanf("%d", &T); for(int t=1;t<=T;t++) { scanf("%d%d", &n, &s); printf("Case #%d: ", t); int sta = max(s,n); if(s==0||s==1||s==2) puts("Yes"); else if( (s+n - sta )>=600) puts("No"); else { init(); x = s+n - sta; for(int i=sta+1; i<=s+n; i++) { for(int j=1;j<=x;j++) { if(i%j==0) add(i-sta+x, j), add(j, i-sta+x); } } int cnt = Hungarian(); if(cnt==x) puts("Yes"); else puts("No"); } } }