Последний номер возведения в степень

У меня небольшая проблема. Задача состояла в том, чтобы принять входные данные для переменной d — что означает количество тестов и выходные переменные a а также b, Каждый тест для другой пары aи b«S. Результатом этого кода должно быть последнее числоб экспоненцирование.
Пример:

//input
2 (it is d)
2 3 (a,b)
3 3 (a,b)

//output
8
7

Вот как я пытался это сделать:

#include <iostream>
#include <cmath>

using namespace std;
int potega(int a, int b);

int main()
{
int d;
int i;
cin >> d;
int t[d];
int a;
int b;
for(i=0; i<=d-1; i++)
{
cin >> a >> b;
t[i]=pow(a%10,b);
}
for(i=0; i<=d-1; i++)
{
cout << t[i]%10 << endl;

}
}

У вас есть какие-нибудь предложения? Я новичок Время выполнения должно быть менее 0,529 с.

0

Решение

Вместо прохождения каждой из сил вы можете использовать разложение числа на квадратные силы.

Таким образом, если вы скажете, что показатель степени 7 равен точно так же, как (1 + 2 + 4), так что вы можете использовать степени 1, 2 и 4 показателя, это значительно ускорит показатель. Если у вас есть показатель степени 9 (8 + 1), вы возводите число в 3 раза, чтобы получить восьмую степень, и вы пропускаете степени 2 и 4 при умножении.

Таким образом, для любых заданных двух чисел вы должны хранить текущую степень числа ^ (2 ^ n) числа и затем проверять, находится ли эта конкретная степень в двоичном представлении b.

Это также известно как возведение в квадрат путем возведения в квадрат, и вы можете прочитать больше об этом на этот вики-сайт. За исключением вашей модификации, вы фактически всегда сохраняете% 10 остальной части числа вместо полного числа.

0

Другие решения

На случай, если кому-то понадобится решение:

/*for any a last number of a^b = last number of a^b+4 so: */
if (b%4==0)
{
b=4;
}
else b=b%4;

улучшена скорость выполнения формы от 1 сек до менее 0,01 сек 🙂

0

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector