CD
И в топку эти степени -2, это для тех, кто ниасилил запомнить одну строчку)
Size: a a a
2020 September 27
V🇺
Расширенный Евклид
сведение к обратному от mod % i
CD
сведение к обратному от mod % i
ась?
IW
Как ты его вообще собираешься применять?
CD
это какое-то жульничество про предпросчет обратных к факториалу? я помню что такое было
V🇺
это какое-то жульничество про предпросчет обратных к факториалу? я помню что такое было
не, это третий способ обратить по модулю после ^(mod-2) и расширенного евклида
CD
Как ты его вообще собираешься применять?
расширенный Евклид решает уравнение a*x + b*y = 1 если gcd(a, b) = 1
a*x + b*y = 1 (mod b)
a*x = 1 (mod b)
a*x + b*y = 1 (mod b)
a*x = 1 (mod b)
V🇺
и единственный, умеющий в предподсчет (возможно частичный / ленивый)
IW
Я знаю что такое расширенный Евклид)
IW
Переслано от Constantine Drozdov
расширенный Евклид решает уравнение a*x + b*y = 1 если gcd(a, b) = 1
a*x + b*y = 1 (mod b)
a*x = 1 (mod b)
a*x + b*y = 1 (mod b)
a*x = 1 (mod b)
CD
Я знаю что такое расширенный Евклид)
А в чем тогда вопрос?
CD
Что делить это умножать на обратный?
IW
Лол, где ты уравнения увидел
IW
CD
и единственный, умеющий в предподсчет (возможно частичный / ленивый)
ну я его видел, но не разбирал в детали
CD
Лол, где ты уравнения увидел
а ты прочитал, что я написал?
CD
ладно, окай, что такое деление по модулю?
CD
x = a/b def. решение уравнения x*b = a
V🇺
ну я его видел, но не разбирал в детали
полезная штука, позволяет для модулей ~10^9 и прекалком на миллион потом обращать за в среднем 2 модульных умножения