c++ themis szybkie potęgowanie

Question

Witam!

Od jakiegoś czasu próbuję rozwiązać zadanie z serwisu themis.lo14.wroc.pl. Niestety w żaden sposób nie potrafię go zrobić. Mój kod, albo wykonuje się za wolno, albo wychodzą złe wyniki. W końcu użyłem gotowego rozwiązania z internetu wstawiając tylko dwie swoje linijki, ale niestety to też nie działa. Treść zadania:

Zadanie

Dla danych liczb a i b, t.że 0<=a, b<= 1'000'000'000, oblicz cztery ostatnie (najmniej znaczące) cyfry z liczby ab

Wejście: a b

Wyjście: Liczba powstała po odcięciu cyfr powyżej cyfry dziesięciu tysięcy z liczby ab

Przykład

Dla danych wejściowych: 2 3

poprawną odpowiedzią jest: 8

Dla danych wejściowych: 10 10

poprawną odpowiedzią jest: 0

A oto mój ostatni kod:

#include<iostream>
using namespace std;

long long pot_szybkie(long long a, unsigned int n)
{
  long long w = 1;

  while(n>0)
  {
    a%=10000;
    if (n%2 == 1) //jesli bit jest = 1
        w *= a;
    a*= a;
    n/=2; //skrócenie o jeden bit
  }
  w%=10000;
  return w;
}

int main()
{
  unsigned int n;
  long long a;
  cin>>a>>n;

  cout<<a<<" do potegi "<<n<<" wynosi "<<pot_szybkie(a, n);

  return 0;
}

Proszę o jakieś wskazówki.

 

Answer 1

Zamiast long long lepiej byłoby skorzystać uint64_t, ponieważ na różnych systemach finalna zmienna może różnie wyglądać (np long long w domyśle powinna być 64 bitowa na widnowsie, ale np na linuxie jest nią już long). uint64_t zapewnia 64-bitowość zmiennej.

Prawdopodobnie output się nie zgadza ze spodziewanym bo jest niepotrzebny komunikat o tym jaka liczba jest podniesiona do jakiej potęgi

Comments

Niestety uint64_t nie działa na themis :/ błąd kompilacji. Natomiast moje rozwiązanie jest już bardzo blisko, jednak nadal coś nie pasuje. Nie mogę sprawdzić na których przykładach wywala złą odpowiedź, ale przechodzi 6 na 10 testów.

---

Zadanie rozwiązane, dziękuję za pomoc! :)

---

hejo.

Jak Ci sie udalo rozwiazac problem?

mozesz pomoc?

pozdr