Доброго времени суток! Дано нескольких чисел порядка 10^12, не являющихся квадратами, произведение которых гарантированно является квадратом некоторого числа. Проблема в том, что, произведение это, очевидно, > 10^20 то есть значительно превышает размер unsigned long long Собственно, вопрос: как из этого произведения вычислить точный корень за как можно меньшее время? Появляется естественное желание раскладывать числа на простые множители, после чего перемножать заново, но их брать степени в два раза меньше. Но разложение таких чисел каждого займет много времени и памяти. Заранее спасибо всем откликнувшимся!
Ответ
Давайте попробуем вот как:
Пусть наши числа a, b, и их разложение на простые множители выглядит так:
Можно посчитать t = НОД(a, b), не раскладывая числа на множители при помощи алгоритма Евклида, тогда
где
Рассмотрим числа
Эти числа обязаны являться квадратами, т. к. каждый простой показатель степени входит либо в a₀, либо в b₀ (ясно, почему?). Из них можно извлечь корень.
Далее,
Всё.
В качестве альтернативного решения: вычислим приблизительный корень типа double из каждого сомножителя. Точность вычисления корня (sqrt(double)) 52 значащих бита, то есть 15 десятичных разрядов. Для чисел точностью в 12 разрядов корень будет около 6 разрядов, то есть точность корня будет 15 - 9 = 6 знаков после запятой. То же для второго сомножителя. Перемножим полученные корни. Точность произведения будет 5 знаков после запятой. Округлив произведение до целого, получим точный результат (для этого достаточен был бы 1 знак после запятой, а у нас их аж 5).
PS: почему бы не включить математическую нотацию здесь, как и на маткоде?
Комментариев нет:
Отправить комментарий