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

возведение в степень по модулю
Автор luckyi, 13 лет назад, По-русски

нужно вычислить a^b mod c. a, b, c до 10^18 2^63-1(если это вдруг принципиально). Как избежать переполнения или без длинки никак?

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

13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
http://codeforces.me/blog/entry/1729
→ Ответить
13 лет назад, # |
← Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Я в подобных случаях пишу A*B==A+A+A+...+A {B*А}  
Дальше так как и в бинарном воведении в степинь,  вместе A^k считаю и A*k
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Да, довольно известный подход. И по ссылке в комментариях он тоже использовался.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится
Eto moi kod  : 
 read(a,b,c); a:=a mod c; 
 res:=1; //  eto otvet
while b > 0 do 
 begin
   if (b and 1 = 1 ) then 
     begin
        res:=(res * a) mod c;
        dec(b);
      end else 
     begin
       a:=(a * a) mod c;
       b:=b shr 1;
     end;
 end;
write(res);
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    На тесте a = 2^32, b = любое значение, например 100, c = a+1 переполнение, не так ли?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -21 Проголосовать: не нравится
      nu sdelai togda Int64(Long Long) :). Nu tam ewe est' otdel'niy slu4ai, esli ograni4eniya do 2^64.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Почитай описание поста. Там требуется реализовать процедуру для чисел, близких к max long long
        → Ответить