Перевод 10-го числа в 2-ое

@adds · Регистрация: 07.09.2011

Author24 — интернет-сервис помощи студентам

Народ обьясните пжлста как работает эта функция(быстрое возведение числа в степень a^d mod n) :

C++

long powmod(long a, long d, long n)
{
    long b = 1;
 
    while (d) 
    {
        if (d % 2 == 0) 
        {
             d /= 2;
             a = (a * a) % n;
        }
        else 
        {
             d--;
             b = (b * a) % n;
         }
     }
     return b;
}

@Thinker · 18.09.2011, 18:48

Думается, что такое еще быстрее работать будет:

C

long powmod(long a, long d, long n)
{
    long rez = 1, b = a;
 
    while (d) 
    {
        if (d & 1)
        {
             rez *= b;
             rez %= n;
        }
        b *= b;
        b %= n;
        d >>= 1; 
     }
     return rez;
}

@adds · 18.09.2011, 19:20 **[ТС]**

Народ объясните этот кусок

C++

 else 
        {
             d--;
             b = (b * a) % n;
         }

silent_1991 · 18.09.2011, 19:46

Не по теме:

adds, и всё-таки вы в СибГУТИ учитесь... Зря обманули в прошлый раз, так бы может-быть помог...

@fidzhi · 18.09.2011, 20:18

Сообщение от adds

Народ объясните этот кусок

C++

 else 
        {
             d--;
             b = (b * a) % n;
         }

Тебе не понятен только данный кусок кода или обязательно в контексте первого поста?

silent_1991
	18.09.2011, 19:46 #4
	Не по теме: adds, и всё-таки вы в СибГУТИ учитесь... Зря обманули в прошлый раз, так бы может-быть помог... 0

	18.09.2011, 20:18