题意
有 (n) 个数 (s+1ldots s+n)，求是否能将这 (n) 个数放到 (1ldots n) 上，且当令原数为 (x)，放到 (y) 位置时有 (x mod y=0)。
不超过 (100) 组数据，(1le n le 10^9,0le sle 10^9)。
题解
看上去很吓人的数据范围，也是一个让你以为这是结论题的数据范围。
但是仔细观察可以发现，当 (s+1ldots s+n) 中有 (2) 个及以上质数时，只有将他们安排到 (1) 位置或者质数自身位置才有 (xmod y=0)。
首先尝试将这两个质数安排到其自身的位置，这要求 ([s+1,s+n]cap [1,n] eq varnothing)，即要求 (s<n)。
那么此时 ([s+1,n]) 就能够安排到自己的位置了，那么就只剩下 ([n+1,s+n]) 和 ([1,s]) 了，可以发现这就是 (s) 和 (n) 交换后的结果。
但是，当 (s) 与 (n) 交换后，或者 (s) 与 (n) 不能交换时，存在 (2) 个或以上质数，那么显然无解了。另外，根据结论，在 ([2,10^9]) 范围内，大约 (300) 个数就会出现一次质数，这里保险起见设 (1000) 个数出现一次质数。
这里又有一个很神奇的问题，ans+=can[i] 前面不能加 if(!match[i])，具体原因未知。
代码
#include<cstdio>
#include<algorithm>
#include<cstring>
const int MAXN=2000+5;
int n,s,match[MAXN],ver,vis[MAXN];
bool can(int x)
{
vis[x]=ver;
for(int i=1;i<=n;i++)
if((s+x)%i==0 && (!match[i]||(vis[match[i]]!=ver&&can(match[i]))))
{
match[i]=x;
return 1;
}
return 0;
}
int main()
{
int T;
scanf("%d",&T);
for(int t=1;t<=T;t++)
{
memset(vis,0,sizeof(vis));
memset(match,0,sizeof(match));
scanf("%d %d",&n,&s);
if(s<n) std::swap(n,s);
if(n>1000)
{
printf("Case #%d: No
",t);
continue;
}
int ans=0;
for(int i=1;i<=n;i++)
{
ver=i;
ans+=can(i);
}
printf("Case #%d: %s
",t,ans==n?"Yes":"No");
}
return 0;
}