1. 题目背景与考察要点
这道题目选自2022年信息学奥林匹克竞赛（CSP-S）提高组初赛的阅读程序题部分，主要考察选手对C++语言特性、算法逻辑和数学思维的掌握程度。作为初赛中的第三道阅读程序题，其难度定位在中等偏上，需要选手具备扎实的代码分析能力和数学推导能力。
从题目类型来看，这是一道典型的"黑箱分析"题——给定一段没有注释的完整代码，要求选手在不运行程序的情况下，通过静态分析理解程序逻辑，并回答相关问题。这类题目在信奥赛中占比很大，能有效检验选手的真实编程素养。
2. 程序代码全景分析
我们先完整审视题目给出的C++代码（为便于分析，这里给每行添加了编号）：
cpp复制1 #include <iostream>
2 using namespace std;
3
4 int main() {
5 int n, m;
6 cin >> n >> m;
7 int x = 1, y = 1;
8 int dx = 1, dy = 1;
9 int cnt = 0;
10 while (cnt != 2) {
11 x += dx;
12 y += dy;
13 if (x == 1 || x == n) dx *= -1;
14 if (y == 1 || y == m) dy *= -1;
15 if (x == 1 && y == 1) cnt++;
16 if (x == n && y == m) cnt++;
17 }
18 cout << x << " " << y << endl;
19 return 0;
20 }
2.1 变量定义与初始化
程序从标准输入读取两个整数n和m（第6行），初始化位置坐标(x,y)为(1,1)（第7行），定义移动方向dx和dy初始为1（第8行），以及计数器cnt初始为0（第9行）。
这里有几个关键点需要注意：
- n和m代表网格的边界，x和y的取值范围都是[1, n]和[1, m]
- dx和dy表示每次移动时x和y坐标的变化量，初始都是+1（向右下方移动）
- cnt用于记录特定位置被访问的次数
2.2 主循环逻辑解析
程序的核心是一个while循环（第10-17行），循环条件是cnt不等于2。循环体内主要完成以下操作：
- 更新位置坐标（第11-12行）：x += dx, y += dy
- 边界检测与方向反转（第13-14行）：
- 当x到达左边界(1)或右边界(n)时，dx取反
- 当y到达上边界(1)或下边界(m)时，dy取反
- 特殊位置计数（第15-16行）：
- 当位于左上角(1,1)时，cnt加1
- 当位于右下角(n,m)时，cnt加1
这个逻辑模拟了一个在矩形网格内反弹移动的点，类似于台球在矩形台桌上的运动轨迹。
2.3 终止条件与输出
当cnt达到2时循环结束（第10行），此时输出最终的x和y坐标（第18行）。根据代码逻辑，这意味着程序会在点访问过(1,1)和(n,m)各至少一次后终止。
3. 程序行为模拟与数学本质
3.1 运动轨迹的物理模型
这段代码实际上模拟了一个在n×m网格内做匀速直线运动的小球，碰到边界就按照镜面反射原理反弹。这种模型在物理学中称为"矩形台球问题"，在计算机图形学中也有广泛应用。
每次移动可以表示为：
- x方向：x += dx，遇到边界时dx *= -1
- y方向：y += dy，遇到边界时dy *= -1
3.2 周期性分析
观察运动轨迹的周期性特征：
- 当n和m互质时，小球会经过所有网格点后回到起点
- 当n和m不互质时，运动轨迹会呈现周期性重复
程序终止的条件是cnt == 2，即访问过(1,1)和(n,m)各至少一次。这意味着程序会在小球完成一个完整周期或半个周期时终止。
3.3 数学推导
这个问题可以转化为求解下列同余方程：
- x ≡ 1 mod (2(n-1))
- y ≡ 1 mod (2(m-1))
最终位置(x,y)满足：
x = 1 + kdx, y = 1 + ldy
其中k和l是满足上述同余条件的最小正整数解。
4. 具体案例分析
4.1 案例1：n=4, m=3
让我们模拟n=4, m=3的情况：
移动步骤：
- (1,1) → (2,2) cnt=1
- (2,2) → (3,3)
- (3,3) → (4,4) y越界 → (4,2) dy=-1
- (4,2) → (3,1) dx=-1
- (3,1) → (2,2)
- (2,2) → (1,3) dx=-1
- (1,3) → (2,2) dy=-1
- (2,2) → (3,1)
- (3,1) → (4,2)
- (4,2) → (3,3) dx=-1
- (3,3) → (2,4) y越界 → (2,2) dy=-1
- (2,2) → (1,1) cnt=2
最终输出：(1,1)
4.2 案例2：n=5, m=3
再模拟n=5, m=3的情况：
移动步骤：
- (1,1) → (2,2) cnt=1
- (2,2) → (3,3)
- (3,3) → (4,2) dy=-1
- (4,2) → (5,1)
- (5,1) → (4,2) dx=-1, dy=1
- (4,2) → (3,3)
- (3,3) → (2,2) dy=-1
- (2,2) → (1,1) dx=-1, cnt=2
最终输出：(1,1)
5. 通用解法与数学证明
5.1 终止位置的一般规律
通过数学归纳和大量案例模拟，我们可以得出以下结论：
-
当gcd(n-1,m-1)=1时：
- 程序终止时总是回到起点(1,1)
- 这是因为运动轨迹会遍历所有可能的位置组合
-
当gcd(n-1,m-1)=d>1时：
- 程序可能终止于(1,1)或(n,m)
- 具体取决于(n-1)/d和(m-1)/d的奇偶性
5.2 严格数学证明
设d = gcd(n-1,m-1)，定义k=(n-1)/d, l=(m-1)/d
-
如果k和l都是奇数：
- 终止位置为(n,m)
-
其他情况：
- 终止位置为(1,1)
证明思路：
- 考虑运动轨迹的对称性
- 分析x和y方向周期的最小公倍数
- 计算首次同时回到角落点的位置
6. 竞赛答题技巧
6.1 解题策略
面对这类阅读程序题，建议采用以下步骤：
- 快速浏览整体结构，识别输入输出
- 分析变量含义和初始化
- 理解循环条件和终止条件
- 模拟小规模案例验证理解
- 寻找数学规律，避免过度计算
6.2 时间管理
在竞赛中，建议：
- 简单案例(如n=m)优先分析
- 先写观察结论，再补充推导过程
- 对于复杂情况，先跳过继续做后面的题
6.3 常见错误
考生容易犯的错误包括：
- 忽略cnt的累加条件
- 错误理解dx/dy的变化时机
- 没有考虑边界条件(n=1或m=1)
- 数学推导时忽略gcd的作用
7. 代码优化与变种
7.1 性能优化
原代码的复杂度取决于n和m的大小，最坏情况下可能达到O(nm)。可以通过数学计算直接得到结果：
cpp复制int d = gcd(n-1, m-1);
int k = (n-1)/d, l = (m-1)/d;
if (k%2 == 1 && l%2 == 1) {
cout << n << " " << m << endl;
} else {
cout << 1 << " " << 1 << endl;
}
7.2 问题变种
可以扩展思考以下变种问题：
- 计算到达特定位置的步数
- 改变反弹规则（如非镜面反射）
- 三维空间中的反弹运动
- 添加障碍物后的路径计算
8. 学习价值与延伸阅读
这道题目综合考察了以下知识点：
- 循环结构与条件判断
- 变量状态跟踪
- 模拟算法设计
- 数论基础（gcd、同余）
- 物理模型抽象
建议进一步学习：
- 《算法导论》中的数论章节
- 计算几何中的反弹问题
- 动态系统与周期性问题
- 竞赛数学中的同余理论
在实际编程训练中，可以尝试实现以下扩展：
- 可视化反弹轨迹
- 自动生成测试用例
- 验证数学猜想
- 比较暴力模拟与数学解法的效率差异