IT
А, тем же числом.
Size: a a a
2020 March 16
IT
А если два таких числа перемножить? А возвести в степень?
Ведь все помодулю n происходит, в чем проблема то
IF
пляски все равно понадобятся - 10**12 это где-то 2**39, можно считать 40
IF
просто пляски умеренные и без лютой длинной арифметики
ВВ
Когда ты начинаешь в С++ прикручивать пляски - они по времени начинают проседать. А еще надо знать, что эти пляски в природе существуют.
нельзя просто написать (10^12 * 10^12) % 10^12
А питон проглотит.
нельзя просто написать (10^12 * 10^12) % 10^12
А питон проглотит.
DD
Ведь все помодулю n происходит, в чем проблема то
Нет никаких проблем. Просто 10**12 * 10**12 > 2^64. А значит нужно написать код, который делает такое умножение по модулю.
ВВ
А это уже не однострочная быстрая команда. Я использовал вариант с рекурсивной функцией. Знаешь как красиво и быстро ?
DD
Быстро - это не использовать возведение в степень, а использовать умножение, где возможно.
АБ
У меня на ноуте задача 3.E решалась на плюсах с типом __int128. А на тестирующей системе ни в одном компиляторе этого типа не оказалось.
ВВ
Быстро - это не использовать возведение в степень, а использовать умножение, где возможно.
мы говорим, что есть A<N - простые числа порядка 10^12,
X = (A*A)%N как посчитать красиво и быстро ? без __int128
X = (A*A)%N как посчитать красиво и быстро ? без __int128
ВВ
до вчерашнего дня я не представлял себе как это посчитать. но это медленно
VR
мы говорим, что есть A<N - простые числа порядка 10^12,
X = (A*A)%N как посчитать красиво и быстро ? без __int128
X = (A*A)%N как посчитать красиво и быстро ? без __int128
простые или натуральные?
ВВ
я специально написал простые, чтобы не придумывали всяких трюков. В общем случае - любые
VR
для простых проще заранее таблицу составить, любым способом, не так уж их и много
DD
мы говорим, что есть A<N - простые числа порядка 10^12,
X = (A*A)%N как посчитать красиво и быстро ? без __int128
X = (A*A)%N как посчитать красиво и быстро ? без __int128
Я не нашёл ничего, кроме https://www.geeksforgeeks.org/multiply-large-integers-under-large-modulo/
VR
вот есть формула
ВВ
и как это тебе поможет в таких условиях ?
VR
и как это тебе поможет в таких условиях ?
т.е берем ((A%N )*(A%N ))%N
АБ
a и b по условию меньше n