题意

有 \(n\) 个数 \(s+1\ldots s+n\)，求是否能将这 \(n\) 个数放到 \(1\ldots n\) 上，且当令原数为 \(x\)，放到 \(y\) 位置时有 \(x \mod y=0\)。

不超过 \(100\) 组数据，\(1\le n \le 10^9,0\le s\le 10^9\)。

题解

看上去很吓人的数据范围，也是一个让你以为这是结论题的数据范围。

但是仔细观察可以发现，当 \(s+1\ldots s+n\) 中有 \(2\) 个及以上质数时，只有将他们安排到 \(1\) 位置或者质数自身位置才有 \(x\mod y=0\)。

首先尝试将这两个质数安排到其自身的位置，这要求 \([s+1,s+n]\cap [1,n]\neq \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\n",t);

			continue;

		}

		int ans=0;

		for(int i=1;i<=n;i++)

		{

			ver=i;

			ans+=can(i);

		}

		printf("Case #%d: %s\n",t,ans==n?"Yes":"No");

	}

	return 0;

}

巴特西

HDU5943 Kingdom of Obsession 题解

题意

题解

代码

最新文章

热门文章