F 现在是消消乐时间

题解

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

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

1.从某个角射出

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

注意到方程的答案不超过 ，而当 取矩形的四个角时取得最大值 ，即 。

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

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

若想消除所有方块则有 ，解得 。

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

2.回到起点

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

解得 ，即 。

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

若想消除所有方块则有 且 ，解得 。

即 时所有能够进入循环的起点均满足条件，这样的点满足颜色与矩形的四个角相异。

3.结论

综上，我们得出结论：

1. 当 时，任意位置均可；
2. 当 时，从矩形的四个角射入；
3. 当 时，任意坐标和不为偶数的位置均可；
4. 当 时，输出 NO。

Bonus：令 为一次发射能清除方块的最大值，求 。

代码

#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");
}