Задача состоит в том, чтобы возвести большое число 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.