Krokodyle- main2

Witam :)
Robię kurs main2, stanąłem na zadaniuhttps://main2.edu.pl/c/kurs-podstaw-algorytmiki-druga-e/p/kro/
Napisałem taki kod:

#include <iostream>

using namespace std;

int a;
int b;
int P;
int iloscOpcji;

int main()
{
    ios_base::sync_with_stdio(false);
    cin>>P;
    for(int i=0; i<P; i++)
    {
        cin>>a;
        cin>>b;
    iloscOpcji = a+1;
    for (int y=1; y<b; y++)
    {
	iloscOpcji *= (a+1);
    iloscOpcji%=10000;
    }
    cout<<iloscOpcji<<"\n";
    }
    return(0);
};

I pojawia się mały problemik- program działa prawidłowo, ale.. za wolno.
Dokładnie o 0.01s.
"1.01s/1.00s"
Prosiłbym kogoś o pomoc w optymalizacji kodu, z góry dziękuje, pozdrawiam!

Bez zmiany algorytmu: wystarczające przyspieszenie powinno Ci dać samo przejście na printf i scanf. Bezmyślne, ale działa.

1. Wywal zmienne globalne
2. cout.tie(nullptr); cin.tie(nullptr);

Możesz łatwo zmniejszyć złożoność wykonując potęgowanie zamiast mnożenia w pierwszym etapie. Tj. rozbić a^b = a^k * a ^ (b-k) gdzie k jest potęgą 2 mniejszą od b. Czyli w pierwzym etapieiloscOpcji *= iloscOpcji, a dopiero potem ```
iloscOpcji *= (a+1).

A jeszcze lepiej zadziała algorytm potęgowania modularnego.

Zastosowałem kod:

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int P;
    cin>>P;
    for(int i=0; i<P; i++)
    {
        int a;
        int b;
        cin>>a;
        cin>>b;
    int iloscOpcji;
    iloscOpcji = a+1;
    for (int y=1; y<b; y++)
    {
    iloscOpcji *= (a+1);
    iloscOpcji%=10000;
    }
    cout<<iloscOpcji<<"\n";
    }
    cout.flush();
    return(0);
};

Lecz mimo tego program nie przyśpieszył do końca- przy pierwszej próbie, wyświetliło mi się 1.00s/1.00s ale i tak z błędem przekroczenia czasu, a przy nastepnej próbie 1.02s/1.00s..

Przynajmniej sprawdź to co Ci napisałem wyżej, tj:

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int P;
    cin >> P;
    for(int i=0; i<P; i++)
    {
        int a;
        int b;
        cin >> a;
        cin >> b;
        int iloscOpcji = a + 1;

        int k = 1;
        while (k * 2 < b)
        {
            iloscOpcji *= (iloscOpcji % 10000);
            iloscOpcji %= 10000;
            k *= 2;
        }

        for (int y = k; y < b; y++)
        {
            iloscOpcji *= (a+1);
            iloscOpcji %= 10000;
        }
        cout << iloscOpcji << "\n";
    }
    cout.flush();
    return(0);
};

Obstawiam, że czas spadnie mniej więcej o połowę, pytanie czy to wystarczy.

Sprawdziłem ten kod co mi podesłałeś, to czas pogorszył się do 1.10s/1.00s

No to
http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html
http://smurf.mimuw.edu.pl/node/836

Dziękuje.
Musiałem zastosować modulo- po zastosowaniu tego algorytmu, program działał 0.01s/1.00s