2

Задача состоит в том, чтобы возвести большое число n ( 0 <= n <= 10^50) в степень m ( 0 < m < 1000). Для этого, безусловно, использую длинную арифметику

typedef vector<long long> largen;

А также бинарное возведение в степень.

largen recbinpow(largen a, int n) {
    largen e;
    e.push_back(1);
    if (n == 0)
        return e;
    if (n % 2 == 1)
        return multiply(recbinpow(a, n - 1), a);
    else {
        largen b = recbinpow(a, n / 2);
        return multiply(b, b);
    }
}

Но это всё равно оказалось слишком медленно. Я выяснил, что если брать основание системы счисления побольше, например 10^9, то возведение в степень будет происходить гораздо быстрее.

const int base = 1000 * 1000 * 1000;

largen  multiply(largen a, largen b) {
    largen c(a.size() + b.size());
    for (size_t i = 0; i<a.size(); ++i)
        for (int j = 0, carry = 0; j < (int)b.size() || carry; ++j) {
            long long cur = c[i + j] + a[i] * 1ll *(j < (int)b.size() ? b[j] : 0) + carry;
            carry = (long long)(cur / base);
            c[i + j] = (long long)(cur % base);
        }
    while (c.size() > 1 && c.back() == 0)
        c.pop_back();
    return c;
} 

Но, по непонятным мне причинам, программа работает некорректно на некоторых значениях, например 999 999 999.

Часы отладки ни к чему не привели. Помогите, пожалуйста, отыскать ошибку programme.

1
  • Если есть написанный алгоритм дискретного преобразования Фурье и свертки, то умножение можно написать почти без пердолинга.
    – typemoon
    16 апр 2016 в 14:57

1 ответ 1

1

А вы не хотите учесть, что ваш вывод

for (int i = result.size() - 1; i >= 0; i--) {
    cout << result[i];
}

должен, вообще-то, выводить еще и ведущие нули (буде таковые имеются)?... Т.е. если ваш элемент вектора меньше того самого миллиарда, то он-то все равно должен выводиться в 9 знакомест?

3
  • Ведущие нули удаляются после каждого умножения. С выводом всё в порядке. 16 апр 2016 в 15:13
  • @KeltarHelviett Я просто в вашей программе ввел 100 и возвел в 20 степень. получил 1 с 8 нулями. Но если ваш вывод переписать вот так: cout << setw(9) << setfill('0') << result[i]; - то получается единица с 40 нулями, как и надо... Так что с выводом у вас точно не все в порядке? это вы погорячились, утверждая, что все OK...
    – Harry
    16 апр 2016 в 15:20
  • Понял свою ошибку. Действительно, нужно было просто дополнять нулями, если число в векторе не состоит из 9 разрядов. Спасибо большое. 16 апр 2016 в 15:42

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.