SPOJ: Zadanie "Czy umiesz potęgować"

Question

Witam,

Napiszę na wstępie, że zdaje sobie sprawę, że umieszczanie gotowych kodów jest niemile widziane, ale wykorzystałem już wszystkie możliwości.

Sędzia nie uznał mi jeszcze żadnego zadania, a próbowałem wrzucić kilkanaście. Zdecydowałem się spytać Was o zadanie "Czy umiesz potęgować", bo jest naprawdę banalne. Myślę, że każdy potrafi je zrobić.

Funkcji pow użyłem, bo podobno jest najszybsza, z racji tego, że napisana w Asemblerze. Wcześniej wypisywałem wynik za pomocą cout, ale zmieniłem na printf... Bez rezultatów.

#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int main() {
		short n,i=1;
		long long int a,b,pot;
		cin>>n;
		while(i<=n) {
				cin>>a>>b;
				pot=pow(a, b);
				printf("%d", pot%10);
				i++;
			}
		return 0;
	}

Proszę uprzejmie o pomoc.

Answer 1

Zrób 1000000 do potęgi 1000000. Twój program będzie bardzo długo liczył a przecież masz limit czasu na spoju. Musisz znaleźć jakąś zasadę tyle podpowiem.

Answer 2

Ze względu na to, że dane wejściowe mogą być bardzo duże, nie ma sensu wykonywania operacji potęgowania, spróbuj na to spojrzeć w inny sposób. W zadaniu pytają jedynie o ostatnią cyfrę, musisz wpaść na pewną zależność, rozpisz sobie na kartce jak zachowują się dane liczby podniesione do kilku kolejnych potęg (dla małych liczb, aby było to widoczne) i zobacz co się będzie działo z ostatnimi cyframi.

Answer 3

Zgodnie z sugestiami zedytowałem swoje rozwiązanie. Nadal jednak jest błąd.

#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int main() {
		short r,n,i=1;
		long long int a,b,pot;
		cin>>n;
		while(i<=n) {
				cin>>a>>b;
if(b==0)
cout<<1;
else if(a%10==0)
						cout<<0;
				else {
						r=b%4;
						if(r==0)
							r=4;
						pot=pow(a, r);
						printf("%d", pot%10);
					}
				i++;
			}
		return 0;
	}

 

Comments

Zrób to "ręcznie", bez używania funkcji pow(), ponieważ dla odpowiednio dużego a, rzędu 10^10 podniesione do potęgi 4 da na tyle dużą liczbę, że ciężko będzie mówić o precyzji z dokładnością do cyfry jedności. Zauważ, że w zależności od tego jaka cyfra jest na końcu, trzeba rozpatrzyć inne przypadki. Kolejne potęgi dwójki to 2, 4, 8, 16, 32, 64, więc ostatnie cyfry to 2, 4, 8, 6, 2, 4... Widzisz już jakąś zależność? Pamiętaj, że nie dla każdej ostatniej cyfry jest taka sama częstość powtarzania się cyfr.

Answer 4

Witam,

tak jak już przedmówcy powiedzieli nie możesz tego liczyć bezpośrednio gdyż obliczenia będą trwać za długo. Musisz zauważyć pewne zależności wśród potęg. Możesz wykluczyć obliczenia obserwując wyniki potęgowania. Np

dla 5) 5 5*5 = 25 5*5*5 = 125 5*5*5*5 = 625 -> tutaj na końcu jest 5 i jak pomnożysz przez 5 zawsze będzie 5

dla 6) 6 6*6 = 36 6*6*6 = 216 6*6*6*6 = 1296 -> można zauważyć że na końcu zawsze jest 6

dla 1) 1 1*1 = 1 1*1*1 = 1 1*1*1*1 = 1 -> łatwo znaleźć zależność.

Twój kod po małym tuningu dla tych trzech powyższych wartości.

#include <iostream>
#include <cstdio>
#include <math.h>
using namespace std;
int main() {
        short n,i=1;
        long long int a,b,pot;
        cin>>n;
        while(i<=n) {
                cin>>a>>b;
                if( a == 1)
                {
                    printf("1\n");
                }
                else if( a == 5){
                    printf("5\n");
                }
                else if( a == 6)
                {
                    printf("6\n");
                }
                i++;
            }
        return 0;
   }

Polecam rozpisać sobie resztę na kartce i znaleźć podobieństwa.

Answer 5

Podepnę się pod pytanie bo jest tag C++ a w sumie nie ma sensu zakładać nowego tematu. 

#include <iostream>
int pow (long int x, long int y)
{
	if(y==0) return 1;
	else return pow(x,y-1)*x;
}
int main()
{
	long int x,y,d;
	std::cin>>d;
	for(int i=0; i<d; i++)
	{
		std::cin>>x,y;
		if(y!=4) y= y%4;
		std::cout<<pow(x, y)% 10<<std::endl;
	}
	return 0;
}

Napisałem taki oto kod ale wciąż zwraca mi błędną odpowiedź jakieś sugestie?

Comments

Przeczytać wszystkie odpowiedzi jakie padły.

Answer 6

#include <iostream>
#include <string>
#include <sstream>
 
 
 
using namespace std;
 
int t,a,b,dlugosc;
string number;
 
int main()
{
    cin>>t;
 
    for(int i=1 ; i<=t ; i++)
    {
        cin>>a>>b;
 
        stringstream liczba;
        liczba<<a;
        string number = liczba.str();
 
        int dlugosc = number.length();
 
        if(number[dlugosc-1]=='0') cout<<"0"<<endl;
        else if(number[dlugosc-1]=='1') cout<<"1"<<endl;
        else if(number[dlugosc-1]=='5') cout<<"5"<<endl;
        else if(number[dlugosc-1]=='6') cout<<"6"<<endl;
 
        if((number[dlugosc-1]=='4')&&(b%2==0)) cout<<"6"<<endl;
        else if((number[dlugosc-1]=='4')&&(b%2!=0)) cout<<"4"<<endl;
 
        if((number[dlugosc-1]=='9')&&(b%2==0)) cout<<"1"<<endl;
        else if((number[dlugosc-1]=='9')&&(b%2!=0)) cout<<"9"<<endl;
 
        if(number[dlugosc-1]=='2')
           {
               if(b==1) cout<<"2"<<endl;
               else if(b%4==0) cout<<"6"<<endl;
               else if((b+1)%4==0) cout<<"8"<<endl;
               else if((b+2)%4==0) cout<<"4"<<endl;
               else cout<<"2"<<endl;
           }
 
           if(number[dlugosc-1]=='3')
           {
               if(b==1) cout<<"3"<<endl;
               else if(b%4==0) cout<<"1"<<endl;
               else if((b+1)%4==0) cout<<"7"<<endl;
               else if((b+2)%4==0) cout<<"9"<<endl;
               else cout<<"3"<<endl;
           }
 
           if(number[dlugosc-1]=='7')
           {
               if(b==1) cout<<"7"<<endl;
               else if(b%4==0) cout<<"1"<<endl;
               else if((b+1)%4==0) cout<<"3"<<endl;
               else if((b+2)%4==0) cout<<"9"<<endl;
               else cout<<"7"<<endl;
           }
 
           if(number[dlugosc-1]=='8')
           {
               if(b==1) cout<<"8"<<endl;
               else if(b%4==0) cout<<"6"<<endl;
               else if((b+1)%4==0) cout<<"2"<<endl;
               else if((b+2)%4==0) cout<<"4"<<endl;
               else cout<<"8"<<endl;
           }
 
}
 
    return 0;
}

Musisz znaleźć zasadę, która pozwoli ci wyznaczać ostatnie liczby bez potrzeby potęgowania ze sobą bardzo dużych liczb. Zamieszczam kod z poprawna odpowiedzią na górze gdybyś jednak potrzebował jakiejś małej podpowiedzi. Pozdrawiam

Comments

Bez sensu, bo to on powinien sam zauważyć zależność i zaimplementować. Poza tym da się skrócić co najmniej 3 razy i zrobić bez stringstream (wystarczy %10, %4 i tablica).

---

Pomyślałem, że kod może być pomocny, a co do długości kodu to celna uwaga, bo też sie dopiero uczę.