Potęga dwójki

Question

Witam.

Mam problem (jakże dość prostym) zadaniem.

Treść zadania

Mój kod:

#include <iostream>

using namespace std;

int main()
{
    long long n,wynik=2;
    cin >> n;
    if(n>=0)
    {
        if(n==0)
        {
            wynik=1;
        }
        else
        {
            for (int i=1; i<n; i++)
            {
                wynik=2*wynik;
            }
        }
    }
    cout << wynik%10;
    return 0;
}

Wg mnie jest wszystko dobrze, jednak sędzia odrzuca mój program. 

Za wskazówki będę bardzo wdzięczny.

Answer 1

Tutaj nie chodzi o liczenie całej liczby( 2^10^18 to bardzo dużą liczba. Nie mieści się w longu ani żadnym innym typie z iostream). Tutaj chodzi o znalezienie zależności między kolejnymi wynikami potęg. To zadanie można rozwiązać przy użyciu jednego modulo i jednego switcha. Więcej nie mogę powiedzieć. Powodzenia!

Comments

Możesz zawsze dopowiedzieć, żeby sobie wypisal kilka potęg dwójki :)

---

Ok, zaraz pomyślę.

---

Dziękuję, a jeszcze pytanie, moje rozwiązanie było dobre, prawda?

Tylko nie obejmowało zbyt wielu liczb, tak ?

---

Rozwiązanie w teorii może działać, ale:

• Jest bardzo wolne (w pesymistycznym przypadku po zaimplementowaniu odpowiedniego typu liczenie tej liczby zajęłoby bardzo dużo czasu. Obliczanie tej liczby na normalnym komputerze na pewno nie skończyłoby się dzisiaj, jutro też nie, możliwe, że za miesiąc też nie)
• Typy których używasz nie pomieszczą liczby 2^10^18 :)

---

#include <iostream>

int main()
{
	long long int n;
	
	std::cin >> n;

	if (n == 0)
	{
		std::cout << 1 << std::endl;
	}
	else
	{
		while (n > 4)
		{
			n -= 4;
			if (n <= 4)
				break;
		}

		switch (n)
		{
		case 1: std::cout << 2 << std::endl; break;
		case 2: std::cout << 4 << std::endl; break;
		case 3: std::cout << 8 << std::endl; break;
		case 4: std::cout << 6 << std::endl; break;
		}
	}

	return 0;
}

W takim razie dlaczego to rozwiązanie jest błędne?

---

Twoje rozwiązanie jest bardzo wolne. Użyj modulo zamiast pętli.