自动搬运

查看原文

来自洛谷，原作者为

	dingcx 不如回头再看一眼题面

搬运于2025-08-24 22:15:17，当前版本为作者最后更新于2020-01-01 18:48:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为$2020$年的第$2$道比赛题，还是比较简单的。

思路

这题代码并不难写，重点在于思路。

先举几个例子。如果环长$8$，步长$2$，会出现这样的情况：

可以发现，当初始点是红点时，蓝色的$4$块永远跳不到，否则红色的$4$块永远跳不到。

如果环长$8$，步长$6$，会出现这样的情况：

和上面效果是一样的。

再如果环长$8$，步长$4$，又会出现这样的情况：

出现了$4$种颜色。

综上，不难发现颜色的个数就是环长和步长的最大公约数。

只要一种颜色有一个格子上有兔子，那么所有这种颜色上都能够跳到。

答案就是跳不到的颜色个数乘以每个颜色有多少格。

这样，代码就呼之欲出了。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

#include<cstdio>
using namespace std;
const int MAXN=1e6+10;
bool s[MAXN];//s[i]表示有没有兔子在颜色i上
int gcd(int num1,int num2){//标准gcd求最大公约数
	if(num2==0) return num1;
	return gcd(num2,num1%num2);//辗转相除法
}
int main(){
	int n,m,d,a,ans=0;
	scanf("%d%d%d",&n,&m,&d);
	int gc=gcd(n,d);//求出颜色个数
	for(int i=1;i<=m;i++){
		scanf("%d",&a);
		s[a%gc]=1;//标记
	}
	for(int i=0;i<gc;i++)
		if(!s[i]) ans+=(n/gc);//跳不到就加上每个颜色的格数
	printf("%d",ans);
	return 0;//华丽结束
}

看我这么辛苦画了这么些个图，总得点个赞再走呀！