499. Czy umiesz potęgować [PA05_POT]

Witam , czy nakieruje mnie ktoś jak usprawnić poniższy kod , by nie wyrzucało mi przekroczenia czasu ?

#include <iostream>

using namespace std;
int how_many=0;
int principle=0;
int index=0;

long int potega(int podstawa, int wykladnik)
{
    if (wykladnik==0)
    {
        return 1;
    }
    else
    {
        return podstawa*potega(podstawa,wykladnik-1);
    }

}
int main()
{
    cin>>how_many;
    for(int i=0;i<how_many;i++)
    {
        cin>>principle>>index;
        cout<<potega(principle,index)%10<<endl;
    }
    return 0;
}

Tego kodu w kontekście tego zadania nie da się usprawnić. Masz tu nie tylko przekroczenie limitu czasu ale masz też, dla niektórych testów, przekroczenie zakresu typu long long, a tym bardziej long int.

PS
Tyle o tym już tu napisano w tym i innych wątkach poświęconych temu zadaniu, że aż dziwne, że nie doczytałeś.

Dzięki , trochę szkoda. Miałem poczytać jak to rozwiązać, ale przyszedł mi jeszcze jeden pomysł użycia funkcji potęgowania z biblioteki cmath . Sknociłem poniższy kod i wyrzuca mi tym razem błędną odpowiedź , więc chyba jest ruch w interesie ma ktoś pomysł co jest powodem błędu?

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long long int how_m=0,bufor=0,index=0,principle=0;

    cin>>how_m;
    for(int i=0;i<how_m;i++)
    {
        cin>>principle>>index;
        bufor=(pow(principle,index));
        cout<<bufor%10<<endl;

    }
    return 0;
}

w tym wątku wyjaśniano to wiele razy (a są też inne wątki poświęcone temu zadaniu)
więc przeczytaj wątek i będziesz wiedział

Zrobiłem sporo testów z tego wątku oraz swoich i niby jest ok. Bardziej ciekawi mnie czy ktoś może wskazać błąd w tym programie (od spoja dostaje błędną odp): https://ideone.com/1Gfl5Z#stdin5

Ogólnie to pisałem algorytm na podstawie: https://www.matematyka.pl/44958.htm10

• najpierw sprawdzamy przypadki brzegowe dla wykładnika = 0 i 1 oraz podstawy = 0
• później liczymy podstawę do 4 potęgi z tego wyciągamy ostatnią cyfrę: liczby[k] = fmod(pow(p, i), 10); Dla przykładu ktoś podał np.16455 44556 to liczę: 16455^1, 16455^2, 16455^3, 16455^4 no i z tych wyników ostatnia cyfra
• sprawdzam ile różnych cyfr jest w 4 elementowej tablicy i ustawiam na tą wartość zmienną licznik
• wyliczam ostatnią liczbę jako liczby[indx]
• kiedy liczby w tablicy się powtarzały zwracam po prostu pierwszą.

OK już mam ten błąd: zamiast liczby[k] = fmod(pow(p, i), 10); powinno być liczby[k] = fmod(pow(p%10, i), 10);

Zdaje sobie sprawę, że mój kod nie jest optymalny. Dziękuję za cenne wskazówki ogólnie to planuje robić przynajmniej 2 zadania ze spoja na tydzień

> #include <iostream>
> 
> using namespace std;
> 
> int main()
> 
> {
> int ile;
> 
> cin >> ile;
> 
> int *tab1 = new int[ile];
> int *tab2 = new int[ile];
> 
> for (int i = 1; i <= ile; i++)
> {
> 	cin >> tab1[i] >> tab2[i];
> 
> }
> 
> for (int i = 1; i <= ile; i++)
> {
> 	if (tab2[i] == 0) cout << 1;
> 	else
> 	{ 
> 	switch (tab1[i]%10)
> 	{
> 	case 0: cout << 0<<endl; break;
> 	case 1: cout << tab1[i]%10 << endl; break;
> 	case 2: 
> 		switch (tab2[i]%4)
> 		{
> 		case 0: cout << 6 << endl; break; 
> 		case 1: cout << 2 << endl; break;
> 		case 2: cout << 4 << endl; break;
> 		case 3: cout << 8 << endl; break;
> 		} break; 
> 	case 3:
> 		switch (tab2[i] % 4)
> 		{
> 		case 0: cout << 1 << endl; break;
> 		case 1: cout << 3 << endl; break;
> 		case 2: cout << 9 << endl; break; 
> 		case 3: cout << 7 << endl; break;
> 		} break; 
> 	case 4:
> 		switch (tab2[i] % 2)
> 		{
> 		case 0: cout << 6 << endl; break;
> 		case 1: cout << 4 << endl; break;
> 		} break;
> 	case 5: cout << 5 << endl; break;
> 	case 6: cout << 6 << endl; break;
> 	case 7:
> 		switch (tab2[i] % 4)
> 		{
> 		case 0: cout << 1 << endl; break;
> 		case 1: cout << 7 << endl; break;
> 		case 2: cout << 9 << endl; break;
> 		case 3: cout << 3 << endl; break;
> 		} break;
> 	case 8:
> 		switch (tab2[i] % 4)
> 		{
> 		case 0: cout << 6 << endl; break;
> 		case 1: cout << 8 << endl; break;
> 		case 2: cout << 4 << endl; break;
> 		case 3: cout << 2 << endl; break;
> 		} break;
> 	case 9:
> 		switch (tab2[i] % 2)
> 		{
> 		case 0: cout << 1 << endl; break;
> 		case 1: cout << 9 << endl; break;
> 		} break;
> 
> 	}
> 
> 
> 	}
> 
> 	
> 
> }
> 
> system("pause");
> return 0;

Mam taki kod, wiem że długaśny, jednak liczy bez wielkich obliczeń i szybko, jednak SPOJ go nie przepuszcza. Gdzie jest błąd?

Postaraj się poprawniej wklejać kod.
Poczytaj o tablicach i indeksach.

PS
Nie istotne, ale na spoju nie nie ma “pause”. Gdyby było/a to miałbyś TLE.

Jak testuje u siebie to wszystko działa poprawnie. Możesz sprecyzować o co chodzi z tymi indeksami i tablicami?

np dla ile = 10
tab1[0]
…
tab1[9]
a nie
tab1[1]
…
tab1[10]

PS
To nie jest poprawne wklejenie kodu

Witam.
Od 2 dni walczę z tym banalnym programem i niestety poległem. Czy mógłbym liczyć na jakąś podpowiedź?
Poniżej kod:

int main()
{
int a,b,D;
unsigned long long wynik;
do
{
    cin>>D;
}
while (D<1 || D>10);
for (int k=0 ; k<D ; k++)
{
    cin>>a;
    cin>>b;

    if (b==0)
    {
        wynik=1;
    }
    else if ((a%10==0) || (a%10==1) || (a%10==5) || (a%10==6))
        {
            wynik=a;
        }
    else
        {
            wynik=1;
            for (int i=0 ; i<b ; i++)
            {
                wynik*=a;
            }
        }
cout<<wynik%10<<endl;
}
return 0;
}

SPOJ wywala błąd związany z limitem czasowym.
Każda podpowiedź będzie na wagę złota.
Z góry dziękuję.

powyżej twojego postu jest blisko setka podpowiedzi - wystarczy je przeczytać

gdybym nie czytał to na nie umieszczałbym tego posta w tym temacie.

Myślę, że @mariusz193 ma rację. W szczególności posty jasno sugerują, że masz mieć O(1).

Witam,
Napisalem taki oto kod:

#include
#include
using namespace std;

int main()
{
int n;
long long int x;
cin>>n;
int *l = new int[n];
int *w = new int[n];

for(int i=0;i<n;i++)
    cin>>l[i]>>w[i];

for(int i=0;i<n;i++){;
    x=pow(l[i],w[i]);
    cout<<"x: "<<x<<endl;
    cout<<x%10<<endl;
}
return 0;

}

Mogby mi ktos powiedziec dlaczego po wpisaniu danych 1 33 4 moj x wynosi 1185920 a nie 1185921?

ten problem był omówiony w tym wątku co najmniej 10 razy (ale raczej więcej) - więc poszukaj odpowiedzi powyżej

SPOJ zaakceptował mi rozwiązanie tego problemu, a tymczasem wiem, że mój kod daje błędny rezultat w Code::Blocks dla niektórych potęg liczb kończących się na 5 (np.: dla 5^2, 5^3, 5^5 daje ostatnią liczbę 4, a dla 5^1 daje 5). Z czego niepoprawny wynik podawany przez codeblocks może wynikać? Kod wydaje się dobry i dla wszystkich innych przypadków daje dobre rezultaty.

to już było kilka razy tłumaczone - nie należy używać codeblocks, ani funkcji pow() dla typu integer

biblioteka matematyczna codeblocks ma błąd i pow(5, 2) daje wynik 24,99999… więc po rzutowaniu na integer jest to 24

Dzieki za odpowiedź. Chociaż w sumie to dziwne, bo jak wpisać bezpośrednio pow(5,2), pow(5,3), pow(5,4) to daje prawidłowy wynik. Jak sprawdzam co wkłada do funkcji pow() to też są to prawidłowe liczny typu int.
Ale ok, przyjmuję, że to jakiś błąd w code::blocks…