矩形的对角线经过的小方格数量-526互联

题目：

对于一个长度为m，宽为n的矩形，均分成m*n的小方格，求从左上角到右下角的对角线穿过多少个小方格？

题解1：

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n = 1, t, a1 = 0, b1 = 0, a2, b2; // n 计数器，a1、b1 上一次统计过的长、宽方向上的整数
    float a, b, x, le, ca, cb; // a、b 长方形的长和宽，x 微小增量，le 对角线长度，ca、cb 长、宽方向上的变化比例

    cout << "输入长方形的长和宽：" << endl;
    cin >> a >> b;

    le = sqrt(a * a + b * b); // 计算对角线长度
    ca = a / le; // 计算长方向上的变化比例
    cb = b / le; // 计算宽方向上的变化比例

    for (x = 0; x < le; x += 0.01) // 以微小增量遍历对角线长度
    {
        t = 0;
        a2 = x * ca; // 根据比例计算当前位置长方向上的整数
        b2 = x * cb; // 根据比例计算当前位置宽方向上的整数

        if (a2 >= a1 + 1) { // 如果当前位置长方向上的整数大于上次统计的整数
            t = 1; // 标记有新的正方形被穿过
            a1 = a2; // 更新上次统计的整数
        }
        if (b2 >= b1 + 1) { // 如果当前位置宽方向上的整数大于上次统计的整数
            t = 1; // 标记有新的正方形被穿过
            b1 = b2; // 更新上次统计的整数
        }
        if (t == 1) // 如果有新的正方形被穿过
            n++; // 计数器递增
    }

    cout << "对角线串过正方形个数为：" << n << endl;

    return 0;
}

题解2：

对于一个长度为 m，宽度为 n 的矩形，均分成 m ∗ n 个小方格，则对角线经过的小方格数量为 m + n − ( m , n ) ，其中( m , n )为 m 和 n 的最大公约数。

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    for (int a = min(m, n); a > 0; a--) {
        if (m % a == 0 && n % a == 0) {
            cout << "result = " << m + n - a << endl;
            return 0;
        }
    }
    return 0;
}

参考文章：

1. https://blog.csdn.net/xiaofei2010/article/details/7563038?ops_request_misc=&request_id=&biz_id=102&utm_term=%E7%9F%A9%E5%BD%A2%E7%9A%84%E5%AF%B9%E8%A7%92%E7%BA%BF%E7%BB%8F%E8%BF%87%E7%9A%84%E5%B0%8F%E6%96%B9%E6%A0%BC%E6%95%B0%E9%87%8F&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-2-7563038.nonecase&spm=1018.2226.3001.4187

2. https://blog.csdn.net/qq_30205523/article/details/100528069

(〃＞＿＜;〃)(〃＞＿＜;〃)(〃＞＿＜;〃)