每日c/c++题 备战蓝桥杯（小球反弹）[运动分解求解，最大公约数gcd]

试题B: 小球反弹题解

​​​​​​​​​​

❌错解分析

部分同学可能会尝试直接模拟每次碰撞的坐标变化，直到坐标回归原点。但这种方法存在明显缺陷：

1. 实现过程繁琐，需处理大量碰撞计算
2. 碰撞点坐标可能为浮点数，在非常多次碰撞后会产生显著精度损失

✅正解思路

|运动分解分析法|

核心公式：

$S=t\times V_{合}$

其中：

• $t$ 为小球返回原点所需总时间
• $V_{合}$ 为合速度
• $S$ 为题目要求的总路程

这里的$V_{合}$ 可以直接用$dx$ 和$dy$ 合成，易求得，所以只需要探讨$t$ 怎么求即可

运动分解：
将运动分解为x、y两个正交方向：

1. x方向经过$p$个完整来回（$2p$次横跨）
2. y方向经过$q$个完整来回（$2q$次纵跨）

需要注意的是，题目给的分速度是比的形式，但我们仍然可以看作dx是15，dy是17，因为以宏观来看，速率不影响小球经过了几个来回，总路程也不会因为速率的变化而改变

那么我们可以得到下面的式子，其中$x$ 是长方形的长，$y$ 是长方形的宽
关键方程：
$$\{\begin{array}{l}t\cdot dx=2p\cdot x\\ t\cdot dy=2q\cdot y\end{array}$$

比例关系：
通过方程相除消元得到：
$$\frac{p}{q}=\frac{y\cdot dx}{x\cdot dy}$$

最小解推导：
事实上，我们可以把$p=y\ast dx$，$q=x\ast dy$，因为在这个情况下，等式也成立，也就是说小球依然是回到了原点，只不过不知道是第几次回到原点

我们以宏观的角度看，当上式的右边的分子分母为最简的时候，就是小球第一次回到原点的情况

那么现在的工作就是求等式右边分子分母的最大公约数的问题了

设：
$$\begin{array}{rl}p& =\frac{y\cdot dx}{\gcd (y\cdot dx,x\cdot dy)}\\ q& =\frac{x\cdot dy}{\gcd (y\cdot dx,x\cdot dy)}\end{array}$$
此时$p$和$q$为满足比例关系的最小整数解

总时间计算：
代入任意方向方程求时间：
$$t=\frac{2p\cdot x}{dx}=\frac{2q\cdot y}{dy}$$

总路程计算：

$S=t\ast \sqrt{d{x}^2+d{y}^2}$

算法实现步骤

1. 计算$y\ast dx$ 和$x\ast dy$ 的最大公约数 $tem$
2. 代入公式计算最小回归时间$t$
3. 输出结果保留2位小数

方法优势

1. 规避浮点运算：全程使用整数运算，彻底消除精度误差
2. 时间复杂度$O(1)$：仅需计算最大公约数(GCD)，效率极高

代码

#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y)
{
    int tem=x%y;
    while(x%y)
    {
        x =  y;
        y = tem;
        tem = x%y;
    }
    return y;
}
int main()
{
    int dx=15,dy=17,x=343720,y=233333;
    int p,q;
    p = y*dx;
    q = x*dy;
    int tem = gcd(p,q);
    p /= tem;
    q /= tem;
    int t = 2*p*x/dx;
    double ans = t * sqrt(15*15+17*17);
    printf("%.2lf", ans);
    return 0;
}

输出结果

1100325199.77

复杂度分析

• 时间复杂度：$O(\log (\min (ydx,xdy)))$（辗转相除法求gcd）
• 空间复杂度：$O(1)$

注意事项

• 注意处理浮点数输出精度
• 确保使用64位双精度浮点数存储结果
• 特判输入为0的情况（但题目保证输入为正整数）

总结

通过上述方法，我们可以准确计算出小球运动的总路程，并保留两位小数作为最终答案。这种方法避免了浮点数精度损失的问题，同时简化了计算过程，提高了效率。