Как рассчитать, как высоко x должно быть в (x * y)% z перед повторением чисел

Я пытаюсь составить уравнение для вычисления того, сколько раз будет выполняться приведенный ниже код (y и z — константы), прежде чем он начнет повторяться.

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

Например, если значения равны 100, а z равно 360, код будет выполняться 18 раз, прежде чем вывод снова станет равным 0.

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

-2

Решение

Это больше математическая проблема, чем проблема программирования, но здесь идет:

Вам нужно соблюдать одну ключевую вещь: (A * B)% C будет нулевым, если A, B или A * B делится на C без остатков. Итак, одна вещь, которую вам нужно найти, — это наименее распространенное множество.

Пример: y = 5, z = 12. Ваш цикл будет давать 0 каждые 12 итераций. А в вашем примере 100/360 => 5 / 18. Таким образом, вам нужно, чтобы х было 18, так как 5 и 18 взаимно просты, т.е. A * B должен быть равен нулю.

Есть много алгоритмов, чтобы найти наименьшее общее кратное 2 числа. Я поделюсь одним из Вот.

1

Другие решения

Это называется наименьшим общим кратным. Для вашего примера, LCM x = 100 и y = 3600 — 1800 / x = ваши 18.

станд: LCM существует с C ++ 17.

Если вы не можете использовать это, проконсультируйтесь C ++ алгоритм для вычисления наименьшего общего кратного для нескольких чисел для некоторых реализаций, хотя ваша может быть проще, чем те, поскольку они поддерживают более 2 входов.

1

По вопросам рекламы [email protected]