Не знаю как исправить проблему с выходом числа за границы допустимых значений long long

275

01 марта 2019, 09:20

Задача популярная. Просто нужно сделать бинарное возведение в степень по модулю. Вот код

int pow(int x, int n, int d) {
    if(n == 0 && x != 0)
        return 1;
    else if(n == 0 && x == 0)
        return 0;
    int p = 2;
    long long ans = x % d;
    while(p <= n){
        ans *= ans % d;
        ans %= d;
        p *= 2;
    }
    if(p - n == 1 && n != 1){
        ans *= x % d;
        ans %= d;
        int aans = (int)ans;
    }
    int aans = (int)(ans % d);
    if(aans < 0)
        aans = d + aans;
    return aans ;
}

То есть в моей функции pow число x нужно возвести в степень n по модулю d. Но проблема возникает, когда d довольное большое, тогда в строчке ans *= x % d происходит выход за границы long long. Совсем не понимаю, как нужно переделать правильно, чтобы, например, проходил тест x = 71045970, n = 41535484, d = 64735492. Подскажите, пожалуйста

Answer 1

Откровенно говоря, копаться в вашем коде особо времени нет, но если все параметры не выходят за пределы int - то long long автоматом достаточно для промежуточных вычислений, ибо больше, чем произведение двух int, в процессе не получется...

Попробуйте вот такой вариант:

int iqpow(int x, int n, int d)
{
    long long res = 1, y = x;
    y %= d;
    for(;n;n>>=1)
    {
        if (n&1) res = (res*y)%d;
        y = (y*y)%d;
    }
    return res;
}

Не разбирался с вашим алгоритмом, но он дает сбои и на малых числах, где можно проверить едва ли не вручную... Например, pow(2,5,64) у вас дает 16, в то время как очевидно, что 2^5 = 32...