Potęgowanie modularne – przekroczenie limitu czasowego

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;
}

Wersja dla kogoś kto by chciał to przeczytać:

#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;
}

do {
	x %= (long long int)m;
	if (b & 1) {
		wynik = x;
		wynik %= (long long int)m;
	}
	x = x; // Wut?!
} while (b >>= 1);

Poza tym masz 2 średniki na końcu

cout <<wynik<<endl;;

Jakoś tak, sama funkcja:

# include <iostream>

using namespace std;

long long modular_exponenation(long long base, long long exponent, long long modulus){
	if (modulus == 1) return 0;
	long long result = 1;
	base %= modulus;
	while (exponent > 0){
		if (exponent % 2 == 1) 
			result = (result * base) % modulus;
		exponent >>= 1;
		base = (base * base) % modulus;
	}
	return result;
}

int main(){
	cout << modular_exponenation(7, 21, 1234) << endl; // > 773
	cout << modular_exponenation(3, 2, 10) << endl; // > 9
	cout << modular_exponenation(4, 3, 10) << endl; // > 4
	return 0;
	}

 x = x; // Wut?! 
...
cout <<wynik<<endl;;

tam chodziło oczywiście o x*=x :), dodatkowy średnik usunięty.

Spróbowałem to zrobić z funkcją, jak sugerował lion137, ale kwestia jeszcze zrobienia pętli na ilość testów t i wpisania zmiennych a,b,m, zrobiłem więc podobnie jak w pierwotnym kodzie.

int main(){
     int t;
     cin>>t;

    for (int i=0; i<t; ++i)
    {
    long long a,b,m;
    cin>>a>>b>>m;
    cout << modular_exponenation (a, b, m)<< endl;
    }
   return 0; }

i jest to samo, to znaczy wyniki wychodzą poprawne, ale już w testach time limit exceeded :/ Jako ciekawostkę dodam, że w całej mojej grupie na 60 prób do tej pory przez cały tydzień, jeszcze nikomu nie zostało to zadanie zaliczone i w większości problem z tym limitem czasowym. Może to kwestia tej pętli na ilość testów i da sie to jakoś szybciej przeliczyć? Bo algorytm samego potęgowania raczej na pewno dobry.

"i jest to samo, to znaczy wyniki wychodzą poprawne, ale już w testach time limit exceeded :/ Jako ciekawostkę dodam, że w całej mojej grupie na 60 prób do tej pory przez cały tydzień, jeszcze nikomu nie zostało to zadanie zaliczone i w większości problem z tym limitem czasowym. Może to kwestia tej pętli na ilość testów i da sie to jakoś szybciej przeliczyć? Bo algorytm samego potęgowania raczej na pewno dobry."

Dziwne, Spróbuj toz optymalizować na maxa, inline function, szybkie typy uint_fast64, flagi optymalizacyjne?

Kompilowane:
g++ -Wall -std=c++11 -Ofast modular_exponeneation.cc

// modular exponenation c++

# include <iostream>
# include <cstdint>

using namespace std;

inline uint_fast64_t modular_exponenation(uint_fast64_t base, uint_fast64_t exponent, uint_fast64_t modulus){
	if (modulus == 1) return 0;
	uint_fast64_t result = 1;
	base %= modulus;
	while (exponent > 0){
		if (exponent % 2 == 1) 
			result = (result * base) % modulus;
		exponent >>= 1;
		base = (base * base) % modulus;
	}
	return result;
}

int main(){
	cout << modular_exponenation(7, 21, 1234) << endl; // > 773
	cout << modular_exponenation(3, 2, 10) << endl; // > 9
	cout << modular_exponenation(4, 3, 10) << endl; // > 4
	uint_fast64_t test;
	
	for (int i = 0; i < 100000; ++i){
		test =  modular_exponenation(100000000, 99999999, 997773);
		}
	cout <<"In loop: "<< test << endl;
	return 0;
	}

Aż tak szybko (0.003 sek.) nie jest, ale w zależności od liczb, do około 0.033 sekundy, czy 32 bitowe czy 64, nie ma znaczenia. Jak to jeszcze przyspieszyć - nie wiem, może jest błąd w zadaniu?

Silent81 napisał(a):

i jest to samo, to znaczy wyniki wychodzą poprawne, ale już w testach time limit exceeded :/ Jako ciekawostkę dodam, że w całej mojej grupie na 60 prób do tej pory przez cały tydzień, jeszcze nikomu nie zostało to zadanie zaliczone i w większości problem z tym limitem czasowym. Może to kwestia tej pętli na ilość testów i da sie to jakoś szybciej przeliczyć? Bo algorytm samego potęgowania raczej na pewno dobry.

To podaj jaki jest limit czasowy, dla jakich danych i jak to jest mierzone (hardware, sposób pomiaru itp.) - może prościej będzie udowodnić, że się nie da :-)