如何计算在重复数字之前 x 必须在 (x * y) % z 中有多高

Question

我正在尝试计算一个公式，用于计算下面的代码(y 和 z 是常量(在开始重复之前将运行多少次。

while (true) {
    std::cout << (x * y) % z << std::endl;
    x++
}

例如，如果 a 为 100，z 为 360，则代码将运行 18 次，然后输出再次变为 0。

int y = 100;
for (int i = 0; i < 19; ++i) {
    std::cout << y*i % 360 << std::endl;
}

Answer 1

这更像是一个数学问题，而不是一个编程问题，但这里是：

您需要观察一个关键事项：如果 A、B 或 A * B 可以被 C 整除而没有余数，则 (A * B( % C 将为零。所以你需要找到的一件事是最小公倍数。

示例：y = 5，z = 12。您的循环每 12 次迭代将产生 0 个。在您的示例中，100/360 => 5/18。所以你需要 x 是 18，因为 5 和 18 是互质的，即。A * B 需要为零。

有许多算法可以找到 2 个数字的最小公倍数。我将从这里分享一个。

Answer 2

这

称为最小公倍数。例如，x=100 和 y=3600 的 LCM 是 1800/x = 你的 18。

STD：LCM截至C++17存在。

如果您不能使用它，请参阅C++算法来计算某些实现中多个数字的最小公倍数，尽管您的算法可能比那些更简单，因为它们支持 2 个以上的输入。