F 现在是消消乐时间

题解

注意到小球的运动轨迹只有两种：从矩形的四个角之一射出，或者回到发射点进入循环。

接下来对两种情况分别讨论：

1.从某个角射出

令小球的初始位置为 $(x,y)$ ，射出时间为 $t$ ，则 $t$ 为满足如下同余方程的最小正整数：

$\begin{cases}t \equiv -x\ ({\rm mod}\ n) \\ t \equiv -y\ ({\rm mod}\ m)\end{cases}$

注意到方程的答案不超过 $lcm(n,m)$ ，而当 $(x,y)$ 取矩形的四个角时取得最大值 $lcm(n,m)$ ，即 $\frac{ij}{\gcd(i,j)}$ 。

我们将网格线的交点按棋盘方式黑白染色，由于小球只能斜向移动，因此小球只能在同色点之间移动。

同时，一个方块恰好由一对同色点相连接，且每条边最多只被经过一次（经过两次即说明小球在出口处反弹），因此小球在 $t$ 的时间内恰好能消除 $t$ 个方块。

若想消除所有方块则有 $t \geq nm$ ，解得 $gcd(n,m) \leq 1$ 。

当 $gcd(n,m)=1$ 时由裴蜀定理可知方程一定有解，故此时射入的小球一定会射出，且在矩形四个角射入的小球恰好能消除所有方块。

2.回到起点

令小球第一次回到起点的时间为 $t$ ，则 $t$ 为满足如下同余方程的最小正整数：

$\begin{cases}t \equiv 0\ ({\rm mod}\ 2n) \\ t \equiv 0\ ({\rm mod}\ 2m)\end{cases}$

解得 $t=2lcm(n,m)$ ，即 $\frac{2ij}{\gcd(i,j)}$ 。

注意到此时小球在有向环上移动，因此在返回起点前最多经过每条边一次，即小球在 $t$ 的时间内同样能消除 $t$ 个方块。

若想消除所有方块则有 $t \geq nm$ 且 $gcd(n,m) \geq 2$ ，解得 $gcd(n,m) = 2$ 。

即 $gcd(n,m)=2$ 时所有能够进入循环的起点均满足条件，这样的点满足颜色与矩形的四个角相异。

3.结论

综上，我们得出结论：

当 $d=n$ 时，任意位置均可；
当 $gcd(n,m)=1$ 时，从矩形的四个角射入；
当 $gcd(n,m)=2$ 时，任意坐标和不为偶数的位置均可；
当 $gcd(n,m)\geq 3$ 时，输出 NO。

Bonus：令 $f(n,m)$ 为一次发射能清除方块的最大值，求 $\sum_{i=1}^{N}\sum_{j=1}^{N}f(i,j)$ $(1 \leq N \leq 10^5)$ 。

代码

#include<cstdio>
#include<numeric>

int n,m,d,k;

int main(){
	scanf("%d%d%d",&n,&m,&d);
	k=std::gcd(n,m);
	if(d==n||k==1)printf("YES\n0 0\nUR");
	else if(k==2)printf("YES\n0 1\nUL");
	else puts("NO");
}

题解 | #现在是消消乐时间#

F 现在是消消乐时间

题解

1.从某个角射出

2.回到起点

3.结论

代码