Две задачи...

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

1) A^B mod C, (1 ≤ A, B, C < 2⁶³).
При меньших входящих числах я решил задачу методом постепенного возведения в квадрат. Но при данных числах задача будет решена частично, потому что в вычислениях есть операция d*d mod c (d-переменная, которая может принимать максимальное значение 2⁶³ -1). Сначала вычисляется d*d и на этом шагу число не помещается в типы данных. Есть ли способ, который помог бы избежать этого?

2) Извлечение корня квадратного ( только целого числа) из длинного числа A.
Я пробывал решить задачу методом половинного деления, но при A=10¹⁰⁰программа уже работает примерно 2 сек. Есть ли алгоритм, который вычисляет корень быстрее и если да, то какой его принцып работы?

Комментарии (13)

Показать архивные | Написать комментарий?

mingaleg

13 лет назад, # |

Насчёт переполнения в умножении: можно использовать бинарное умножение - это как бинарное возведение в степень, но умножение (кэп не дремлет). Ну, то есть a*(2k) = a*k + a*k, a*(2k+1) = a*(2k)+a. И не забывай везде брать модули.

→ Ответить