TLE для больших входов. Как запустить мой код в срок?
Проблема ссылкаhttp://www.spoj.com/problems/LASTDIG/
Сводка-Учитывая 2 неотрицательных целых числа a и b, выведите последнюю цифру a ^ b.
Я попытался с помощью алгоритма найти модульное возведение в степень, используя меньше места в памяти (http://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method), но я получаю ошибку TLE (превышение лимита времени) для моего решения. Какие изменения я должен сделать, чтобы запустить мой код в течение 1 секунды? Обратите внимание, что 10 тестовых случаев должны быть выполнены в течение 1 секунды.
Мое решение:
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
typedef long long LL;
using namespace std;int ME(LL A, LL B)
{
LL c=1;
int E=0;
while(E<B)
{
c=(c*A)%10;
E++;
}
return c;
}
int main()
{
int t;
LL a, b;
vector <int> lDigit(31);
cin>>t;
for(int i=0;i<t;i++)
{
cin>>a>>b;
if(b>=99999)
lDigit[i]=ME(a, b);
else
{
int temp=pow(a, b);
lDigit[i]=temp%10;
}
}
for(int i=0;i<t;i++)
cout<<lDigit[i]<<endl;
return 0;
}
Решение
Алгоритм, который вы используете, будет медленным для больших возведений в степень. Быстрое модульное возведение в степень учитывает биты в показателе степени и требует только O (LG (N)) умножений / делений, тогда как ваш код требует O (N) умножений. При показателе в 1 миллиард разница составляет от 1 до 30. Увидеть Бинарный метод справа налево.
Псевдокод из Википедии — это
function modular_pow(base, exponent, modulus)
Assert :: (modulus - 1) * (base mod modulus) does not overflow base
result := 1
base := base mod modulus
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base := (base * base) mod modulus
return result
Который в C становится
int modular_pow(int base, int exponent, int modulus) {
int result = 1;
base = base % modulus;
while (exponent) {
if (exponent & 1) {
result = (result * base) % modulus;
}
exponent >>= 1;
base = base * base % modulus;
}
return result;
}
В то время как ваш код выполняет цикл while 2 миллиарда раз для показателей в 2 миллиарда, код выше выполняет цикл ~ 32 раза.
Другие решения