Как можно быстро вычислить (x^n)mod y.
Уже когда-то копал этот вопрос и обнаружил теорему Эйлера (теория чисел).
Не относится к вопросу:
Но вся проблема в том, что я учусь в школе, и мы не проходили еще подобных выражений, найденных мною на wiki, и теории чисел.
Объясните пожалуйста:
- Как использовать эту теорему на практике(например, реализация на C).
- (Не так важно, но просто интересно)Кратко значение формулировки на
wiki. Буду рад какой-нибудь статье, etc для тех, кто еще не знаком с теорией чисел и математикой >9 классов.
x %= y; p = 1; for(int i = 0; i < n; ++i) p = (p*x)%y;
. Если большое - то вместо простого умножения пользуемся быстрым возведением в степень – Harry 12 сен '17 в 17:16mod
в цикле а не на каждой итерации, то это было бы нелохой оптимизацией – ampawd 12 сен '17 в 18:41