自动搬运

查看原文

来自洛谷，原作者为

	Ginger_he .

搬运于2025-08-24 22:34:06，当前版本为作者最后更新于2021-10-22 17:05:07，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目描述

在一个 $2n\times 2n$ 的矩阵中走 $k$ 步，每一轮每个点只能走一次，求出经过点 $(x,y)$ 的最少次数。（一轮的定义为经过矩阵中所有的点）

题解

数据范围是 $10^{18}$，显然是一道数学/找规律题。因为矩阵中有 $2n\times2n$ 个点，且必定存在一个点，使得最后经过的点为给定的点，所以我们不难得到此题的公式为 $\dfrac{k}{4n^2}$。
可能有人会对上面的深色字体有疑问，下面我们来简要证明一下：如果从 $(x,y)$ 开始走能遍历整张图，那从最后到达的那个点反向走回来就必定到达 $(x,y)$。现在问题转为证明在 $2n\times2n$ 的矩阵中，从任意一个点开始走都能遍历整张图。
如果我们对这张图进行黑白染色，就会得到 $2n$ 个黑点和 $2n$ 个白点。不难发现，每次操作都是从一个点走到它的异色点，又因为两种颜色的点个数相同，所以必定能遍历整张图，原命题得证。

代码如下：

#include<bits/stdc++.h>
using namespace std;
long long n,k,x,y;
int main()
{
	scanf("%lld%lld%lld%lld",&n,&k,&x,&y);
	printf("%lld\n",k/4/n/n);
	return 0;
}