在重复数字之前如何计算 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

这叫做最小公倍数。对于您的示例，x=100 和 y=3600 的 LCM 为 1800 / x = your 18.

std:lcm 从 C++17 开始存在。

如果您不能使用它，请参考 C++ algorithm to calculate least common multiple for multiple numbers 了解一些实现，尽管您的实现可能比那些更简单，因为它们支持 2 个以上的输入。

Answer 2

这与其说是编程问题，不如说是数学问题，但是这里是：

您需要注意一件关键事情：如果 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 个数的最小公倍数。我将分享 here.

中的一个

How to calculate how high x has to be in (x * y) % z before numbers are repeated