题意：给定n个人，n个座位，人的编号是【1，n】，座位的编号是【s+1，s+n】，编号为i的人能坐在编号为j的座位上的条件是j%i=0
问是否存在一组方案使得座位和人一一对应
n,s<=1e9
思路：首先考虑如果区间【1，n】和【s+1，s+n】有重叠则重叠部分必然座位和人两两编号相同对应，因为这样能使解的空间更加宽松
现在考虑两端无重叠且等长的区间，显然如果靠后那段区间中出现了质数则必然无解
根据质数密度分布可以近似算出阈值（据tls说是60？），如果区间长度大于阈值则必然无解，否则跑二分图最大匹配
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef long double ld; 7 typedef pair<int,int> PII; 8 typedef pair<ll,ll> Pll; 9 typedef vector<int> VI; 10 typedef vector<PII> VII; 11 typedef pair<ll,ll>P; 12 #define N 2000000+10 13 #define M 200000+10 14 #define INF 1e9 15 #define fi first 16 #define se second 17 #define MP make_pair 18 #define pb push_back 19 #define pi acos(-1) 20 #define mem(a,b) memset(a,b,sizeof(a)) 21 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 22 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 23 #define lowbit(x) x&(-x) 24 #define Rand (rand()*(1<<16)+rand()) 25 #define id(x) ((x)<=B?(x):m-n/(x)+1) 26 #define ls p<<1 27 #define rs p<<1|1 28 #define fors(i) for(auto i:e[x]) if(i!=p) 29 30 const int MOD=998244353,inv2=(MOD+1)/2; 31 //int p=1e4+7; 32 //double eps=1e-6; 33 int dx[4]={-1,1,0,0}; 34 int dy[4]={0,0,-1,1}; 35 36 int head[N],vet[N],nxt[N],match[N],flag[N],a[N],b[N],tot; 37 38 int read() 39 { 40 int v=0,f=1; 41 char c=getchar(); 42 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 43 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 44 return v*f; 45 } 46 47 ll readll() 48 { 49 ll v=0,f=1; 50 char c=getchar(); 51 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 52 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 53 return v*f; 54 } 55 56 void add(int a,int b) 57 { 58 nxt[++tot]=head[a]; 59 vet[tot]=b; 60 head[a]=tot; 61 } 62 63 int dfs(int u) 64 { 65 flag[u]=1; 66 int e=head[u]; 67 while(e) 68 { 69 int v=vet[e]; 70 if(!match[v]||!flag[match[v]]&&dfs(match[v])) 71 { 72 match[v]=u; 73 return 1; 74 } 75 e=nxt[e]; 76 } 77 return 0; 78 } 79 80 int main() 81 { 82 //freopen("1.in","r",stdin); 83 //freopen("1.out","w",stdout); 84 int cas=read(); 85 rep(v,1,cas) 86 { 87 int n=read(),s=read(); 88 int x1,y1,x2,y2; 89 if(n<s+1) x1=1,y1=n,x2=s+1,y2=s+n; 90 else x1=1,y1=s,x2=n+1,y2=s+n; 91 if(y1-x1>100) printf("Case #%d: No\n",v); 92 else 93 { 94 int n=0; 95 rep(i,x1,y1) 96 { 97 n++; a[n]=i; 98 } 99 n=0; 100 rep(i,x2,y2) 101 { 102 n++; b[n]=i; 103 } 104 rep(i,1,n) head[i]=match[i]=0; 105 tot=0; 106 rep(i,1,n) 107 rep(j,1,n) 108 if(b[j]%a[i]==0) add(i,j); 109 int ans=0; 110 rep(i,1,n) 111 { 112 rep(j,1,n) flag[j]=0; 113 if(dfs(i)) ans++; 114 } 115 if(ans==n) printf("Case #%d: Yes\n",v); 116 else printf("Case #%d: No\n",v); 117 } 118 } 119 return 0; 120 }