别样的弹弹球大战

· · 题解

文章前面是关于错误做法的心路历程，可以跳过。

一天，CF duel 给我随机跳题，它问我：“给定一个 n \times m 的棋盘，在上面放球斜向推出，你会不会求路径个数？”我豪爽地答应了：“我当然会！今天上午我就解决。”

我原本以为我上了分讨，它应该会被我轻松解决，可正当这时，一个 Wrong Answer 跳了出来，原来是我讨论错了，一看，是在棋盘两个对角之间的路径错了，它还真有 Hack。我手玩了 Hack，假完了，我仿佛听到 CF duel 在说：“小废物，你怎么连做法都看不出来，再这样下去就要退役了。”

第一回合，我发现了一个显然的性质是，称 x 为 1 或 n 和 y 为 1 或 m 的格子为边界上的格子，任何一条轨迹一定经过边界上的格子。这看起来是一句废话，但是说明可以把考虑轨迹转化为考虑边界上的格子。令球从边界上的格子处出发，由于反弹会经过一组边界上的格子，要求的就是这个组数。

第二局，我进一步地发现，一条轨迹至少会经过四个边界上的格子各一个（不妨认为角上的格子同属于两个边界）。于是只需要考虑一个边界上的格子。

由于 n 与 m 互换对答案没有影响，可以当 n \leq m 推导。

令一个球从左侧出发，弹到右侧再弹回来，一轮移动的次数显然是 2(m-1)。画个图可以发现弹回来的位置以及再次反弹的方向与模 2(n-1) 的余数有关（因为有向右上和右下两种方向，所以要乘以 2），轨迹具有周期性。

那么，当弹回来与最初弹出去方向相同，位置相同时若进行了 k 轮弹至右侧再返回，必定满足 2(n-1)\mid 2k(m-1)，可以把左右两边的 2 约去得到 (n-1)\mid k(m-1)。

可以得到 k 为 \dfrac{n-1}{\gcd(n-1,m-1)}。因为弹过去再返回，每一轮去和返是两个不同的方向，所以总的轨迹数量就是 \lceil\dfrac{2n}{2k}\rceil（最左边有 2n 个方向），也就是 \dfrac{2(n-1)}{2k}+\lceil\dfrac{2}{2k}\rceil=\gcd(n-1, m-1)+1。

但是这里为什么有一个上取整呢？我们僵持了十几组小样例，我因为在脑子里空想，被它击败了。

从那以后，我就不空想了。我认真研究了 2k 的性质，用 GeoGebra 的网格画图，研究出了一套方案。

过了一会，我们举行第三局，它使用 2k \nmid 2n 的样例，对我发动猛烈的攻击，我们势均力敌，平分秋色。我们比了 3 组样例，也没分出胜负。

后来，它不知不觉的被我手玩出来了，我趁着这个好机会，发现 2k \nmid 2n 是因为对角之间的路径不会占到 2k 个方向。一发提交，一遍 AC，对它的打击比被 down 还大。