499- Czy umiesz potęgować?

[robaczarnia]

Witam
Mecze się nad tym zadaniem cały dzień, wszystko w porzadku niby działa, lecz sędzia wywala blądną odpowiedź. Przerabiałem na milion sposobów, lecz nadal to samo, jestem bezradny. Potrzebuje pomocy, z góry dziekuje .

KOD:

#include <iostream>

using namespace std;


int potega(int a,int b)
{
   unsigned long long p=1;
   if(a==0) return 0;
   else
   {
   if(b==0)
   {
    return 1;
   }
   else{
   switch(b%4)
   {
   case 0:
    for(int i=0;i<4;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
    case 1:
    return a%10;
    break;
    case 2:
    for(int i=0;i<2;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
    default:
    for(int i=0;i<3;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
   }
}
}
}
int main()
{
    int D;
    int a,b;
    cin>>D;
    for(int i=0;i<D;i++)
    {

    cin>>a>>b;

    cout << potega(a,b)<< endl;

    }
    return 0;
}

[bosswell]

0 do potęgi 0 wynosi 1

[robaczarnia]

Dziękuję za odpowiedź, poprawiłem błąd, lecz nadal to samo, błędna odpowiedz

#include <iostream>

using namespace std;


int potega(int a,int b)
{
   unsigned long long p=1;
   
   
   if(b==0)
   {
    return 1;
   }
   else{
   switch(b%4)
   {
   case 0:
    for(int i=0;i<4;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
    case 1:
    return a%10;
    break;
    case 2:
    for(int i=0;i<2;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
    default:
    for(int i=0;i<3;i++)
    {
        p=p*a;
    }
    return p%10;
    break;
   }

}
}
int main()
{
    int D;
    int a,b;
    cin>>D;
    for(int i=0;i<D;i++)
    {

    cin>>a>>b;

    cout << potega(a,b)<< endl;

    }
    return 0;
}

[narbej]

np
10000001 4
i tak dalej.
Wychodzi poza zakres unsigned long long - musisz jeszcze coś poprawić - przemyśleć.

PS
Twoją funkcję [po poprawieniu tego czegoś] można napisać dużo prościej, bez switch i tylko z jedną pętlą:

if (b ==0)
    return .... //jak tu jest return, to dalej nie potrzeba else
b = b % 4;
p = 1;
if (b == 0) b = 4;
for (int i = 0; i < b; ++i)
  p *= a;

return ...

PS 2
A jeżeli koniecznie chcesz, ze switch, to np tak:

case 0:
    p = a*a*a*a;

break;
case 3:
p = aaa;
break
itd
return p%…

PS 3
A jeszcze chytrzej [ze switchem]:
p = 1;
…
case 0:
p *= a;
case 3:
p *= a;
case 2:
p *= a;
case 1:
p *= a;
default //
break; //dopiero tu jeden break lub od razu return p%…
return p…

[robaczarnia]

Wow, dzieki za odpowiedź, naprawde bardzo dużo mi dała, w życiu bym nie pomyślał w ten sposób. Zadanie ostatecznie udało mi się rozwiązać wykorzystując potęgowanie szybkie, z mod.

[narbej]

Tam jeszcze poprawiłem w swichach: case 4 na case 0, bo na początku miałeś if b ==0, więc następne po dzieleniu modulo, zero jest ......

[gorodecki5]

Czesc moze mi ktos pomoc rozwiazac problem. Wydaje mi sie ze dziala poprawnie. Odklejam ostatnia cyfre z liczby i z wykladnika i na ich podstawie okreslam ostatnia liczbe. Jednak pokazuje mi blad. Moze jakies testy... Albo jakis babol sie wkradl
Oto link link usunieto problem rozwiazany.

[sig]

W ten sposób nie zrobisz tego zadania, musisz wymyślić lepszy algorytm.

np
3 do potęgi 3 - ostatnia cyfra siedem
3 do potęgi 13 - ostatnia cyfra 3, a twój algo potratował by je chyba tak samo.

Poczytaj choćby ten wątek, to co tu jest powinno cię naprowadzić na prawidłowy algorytm do tego zadania

[gorodecki5]

Dokonalem drobnych zmian w modulo i pokazuje poprawne wyniki. Dzieki wielkie

[armec]

Witam. Podpinam się pod temat bo mam podobny kod jak użytkownik robaczarnia. Wyskakuje mi cały czas, że jest błędna odpowiedź a nie mogę znaleźć błędu. Prosiłbym was o jakieś rady bo nie mam pomysłu co tam jest źle.

  tu był kod

[krystian01]

Test:
11
1289312391 0
1 2321323123
2 324324345
3 435435436
4 9080237
5 2163062
6 96123412
7 921638125
8 2128963591
9 21538123
0 182931253

Twój out:
1
1
1
1
1
1
1
1
1
1
1

Prawidłowy out:
1
1
2
1
4
5
6
7
2
9
0

[armec]

Witam ponownie. Dane które podałeś nie do końca pasują do treści zadania (liczby z zakresu 1 do 1 miliarda) ale naprowadziły mnie na mój błąd. Przekraczałem zakres zmiennej int i zmiana typu pomogła. Dziękuje i pozdrawiam.

[tsw1993]

Podpinam się pod post.
Otrzymuje poprawne dane na wyjściu, zakres nie jest przekroczony. Wydaje mi się że wszystko jest dobrze. Po przesłaniu otrzymuję: błąd wykonania (NZEC) Ktoś podpowie, co robię źle?
Poniżej przesyłam kod (Python3):

def potega (x,y):
if y==0: return 1
else:
return (x*(potega)(x,(y-1))%10)

D = abs(int(input()))
i=1
while (i<=D):
a,b = input().split()
print(potega(abs(int(a))%100,abs(int(b))%100))

[tarpauwatratar]

Nie znam sie za bardzo na Pythonie, ale...

Wczytujesz liczbe danych na wejsciu a potem kolejne liczby z wejscia - ok. Nie wiem po co jest ten abs, ale niech bedzie ze spoj wymaga czy cos tego typu. W kazdym razie przepisalem po kolei Twoj skrypt i interpreter podolal.

Za to funkcji kompletnie nie pojmuje. Rozumiem print(potega(abs(int(a)),abs(int(b)))), ale tu modulo 100 tam modulo 100 tam modulo 10... Do tego rekurencyjne wywolywanie potegi?!

Nie wiem jaki masz pomysl na to zadanie, ale rozwiazanie jest w czasie O(t), gdzie t to liczba testow. Jak wolisz odpowiedz dla kazdej pary liczb jest w O(1). Mysle ze powyzsza funkcja dziala wolniej...

Poza tym dla maksymalnych wartosci a i b uzyskalem bledna odpowiedz.

[narbej]

Ktoś podpowie, co robię źle?

1. Źle wklejasz [przesyłasz] kod.
2. Źle testujesz.
3. Żle używasz pętli.

[thezimny]

Czy może ktoś mi pomóc? Przekracza limit czasu
https://ideone.com/PEajTG

[narbej]

Czy może ktoś mi pomóc?

Jak?

Przekracza limit czasu

Na moje oko, ten twój knod, daje WA, a nie TLE, ale przy odrobinie szczęścia do testów, TLE też jest możliwe.

[thezimny]

Bardziej chodzi mi o podpowiedź co zrobiłem źle

[j4rooo]

Oprócz tego błędu, który robi każdy czyli liczysz potęgę, tylko tak żeby się sędzia nie zorientował (?):

cin >>a >>b;

int x=a;
for(int i=1;i<b;i++)
{
    a*=x;
}

to wypisujesz spacje zamiast wyniku dla a <= 10.

[thezimny]

NIe wiem co ja miałem w głowie dając ten warunek a>10. To jak moge poznać liczbe jedności bez liczenia potęgi?