Hej, proszę o poradę, mój kodzik w zasadzie wyniki podaje dobre, ale nie przechodzi testów, bo przekraczam na części testów limit czasu 1s. Macie pomysł, co tam poprawić?
Chodzi o obliczenie a do potęgi b. Ponieważ wynik może być duży, wynik trzeba podać modulo m.
W pierwszej linii wejścia dana jest liczba całkowita t (1 ≤ t ≤ 100000) określająca liczbę testów. Każdy test dany jest przez trzy liczby całkowite: a, b, m określone wyżej (1 ≤ a ≤ 100000000, 0 ≤ b ≤ 100000000, 1 ≤ m ≤ 1000000.
Na wyjściu należy wypisać t wierszy. W każdym wierszu odpowiedź na zapytanie: (a do potęgi)%m.
Przykład
Dla danych wejściowych
2
3 2 10
4 3 10
poprawną odpowiedzią jest
9
4
#include <iostream>
using namespace std;
int main()
{
int t;
cin>>t;
for (int i=0; i<t; ++i)
{
int a,b,m;
long long int x,wynik=1;
cin>>a>>b>>m;
x=(long long int) a;
do
{
x%=(long long int)m;
if (b&1) {
wynik*=x;
wynik%=(long long int)m;
}
x*=x;
} while (b>>=1);
cout <<wynik<<endl;;
}
return 0;
}