Блог пользователя Crysis

Две задачи...
Автор Crysis, 12 лет назад, По-русски

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

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Насчёт переполнения в умножении: можно использовать бинарное умножение - это как бинарное возведение в степень, но умножение (кэп не дремлет). Ну, то есть a*(2k) = a*k + a*k, a*(2k+1) = a*(2k)+a. И не забывай везде брать модули.
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

1) Умножать два числа можно так же как и возводить в степень. Например

 a· b = (a / 2)·(b / 2) + (a%2)· b / 2 + a / 2· (b%2) - (a%2)·(b%2)
2) Какой-то у вас странный бинпоиск. Казалось бы 1003 должно летать. Тем более что можно сделать основание не 10, а 109 и тогда будет вообще 100*112
→ Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

А насчёт второй: можно написать алгоритм вычисления квадратного корня в столбик

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Чесслово, я такое делал всего один раз в своей жизни. Елена Владимировна, чего уж...
    → Ответить
»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится -16 Проголосовать: не нравится

sqrt(x)=x^(1/2)=e^(ln(p^(1/2)))=e^(ln(p)/2)
а x можно сделать double'ом
тогда на Си это будет выглядеть exp(log(x)/2)

UPD Извините, видимо, неправильно понял задачу

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задачу-то ты правильно понял, просто точности double не хватит.
    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Жаутыковская олимпиада 2009 ?
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет,  в областной Интернет-олимпиаде вторая задача была.
    → Ответить
»
12 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

1) обсуждалось здесь Перемножение long long по модулю

2) можно почитать этот алгоритм acmp.ru, он даже роботает на 10^3000

вторую задачу можно здавать здесь Длинный корень там 10^100

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Спасиба за алгоритм к второй задаче, теперь работает быстро...
    → Ответить