8237 подписчиков
Как определить делимость огромных чисел?
Например, попадается вам задачка о том, делится ли число, равное 39^12-39^11 на 38.
Как быть? Возводить всё в эти огромные степени?
Ни в коем случае! Лучше воспользоваться возможностью вынести общий множитель за скобки.
Общий множитель, правда, тоже большой - 39 в 11-й степени. Ну, так что же? Какой уж есть, такой и выносим.
И тогда получаем выражение:
39^11(39 - 1)
А это, очевидно, равно 39^11*38.
Ну, а если мы имеем произведение, в котором один из множителей это 38, то оно точно делится на 38. :)
Вот и вся задача!
Около минуты
7 июля 2022
639 читали