Jest to zadanie ze SPOJ i nie mam pojęcia jak dokończyć, a muszę wyznaczyć ostatnią cyfrę liczby wyniku z potęgowania. Może wy mnie jakoś nakierujecię bym dał rade rozwiazać to.. ? Wynik np. 27 i ma byc widoczna tylko 7.
#include <iostream>
#include<math.h>
using namespace std;
int main()
{
int a,b,ile;
cin>>ile;
for(int i=1; i<=ile; i++)
{
cin>>a>>b;
cout<<pow(a,b)<<endl;
}
return 0;
}
modulo z 10. Zawsze da Ci ostatnia liczbe
#include <stdio.h>
int main()
{
unsigned T,a,b;
for(scanf("%u",&T);T--;printf("%c\n",(10*(b&3)+(a%10))["0161656161012345678901496569410187456329"])) scanf("%u%u",&a,&b);
return 0;
}
nie, ma zrozumieć, że ponieważ problem tak blachy że da się zrobić w jednej linijce, to jak porządnie się zastanowi to sam da radę zrozumieć i napisać. Jeśli chcesz, żeby się porządnie zastanowił, to po pierwsze nie dawaj gotowców. Dwa że IMHO takim postem jedyne co uzyskasz, to konfuzję u OP. Zastanowić się (być może) zastanowi, ale nie dzięki Twojemu postowi, bo nie zrozumie wiadomości, którą chciałeś mu przekazać. Skoro nawet @bogdans musiałeś tłumaczyć jak należy rozumieć Twojego posta, to tym bardziej OP. Bo OP słabiej Cię zna a więc i komunikacja gorsza.
tym razem wykazał mi sędzia "przekroczono limit czasu"
#include <iostream>
using namespace std;
long int potega(int p, int w)
{
if (w==0) return 1;
else return p*potega(p,w-1);
}
int main()
{
int ile,p,w;
cin>>ile;
for(int i=1; i<=ile; i++)
{
cin>>p>>w;
cout<<potega(p,w)%10<<endl;
}
}
No a co ci ma wypisać? Nie przeczytałeś ze zrozumieniem żadnego postu w tym temacie chyba. Nadal potęgujesz te liczby, do tego jeszcze rekurencyjnie o_O Nie zrozumiałeś tego co bodans napisał?
123456789123456789 ma taką samą ostatnią cyfrę jak 99. Nie trzeba wykonywać całego takiego mnożenia żeby poznać wynik. Jakbym sie ciebie zapytał jaka jest ostatnia cyfra liczby:
123456789123456789*1234567890 to też byś to najwpierw wszystko wymnożył dokładnie?
W ten sposób tego nie zrobisz, wychodzą takie wyniki że nie mieszczą się w żadnej dostępnej w c(++) zmiennej. Python "twierdzi" że np 8 do potęgi 100 ma 91 cyfr, a tym danym wejściowym przecież daleko do maksymalnych.
p i w, to 10^9. Trzeba zatem znaleźć miejsce na liczbę mającą 1+10^18 cyfr. Nawet Python polegnie.
Dodam jeszcze, że komunikat sędziego był inny niż "przekroczono limit czasu". Ten kod ma błąd składniowy, więc programu się nie uruchomi. Trochę Ci podpowiem, zamiast
cin>>p>>w;
cout<<potega(p,w)%10;<<endl;
daj
cin>>p>>w;
p = p % 10;
cout<<potega(p,w)%10<<endl;
Może już wystarczyć, jeśli nie, to podrasuj funkcję potega.
Kod wkleiłem taki jak podałem "Wam". Nie mam w zwyczaju oszukiwać, zwłaszcza osób które proszę o rade ale to moje stanowisko nie każdy musi taki być.
<img src=http://naforum.zapodaj.net/thumbs/ab6fdf5acde5.jpg alt=hosting zdjęć zapodaj.net />
Ale już dość, zbytnio oddaliłem się od tematu który mnie interesuje.
Najprostsze (najszybsze to już podałem) co powinno przejść to:
cin>>p>>w;
cout<<((int)pow(p%10,4+w%4))%10<<endl;
A teraz już Ci zarzucę kłamstwo, założyłem konto na SPOJ-u, wysłałem Twój kod i zobaczyłem to: 
.
_13th_Dragon napisał(a):
Najprostsze (najszybsze to już podałem) co powinno przejść to:
cin>>p>>w;
cout<<((int)pow(p%10,w%4))%10<<endl;
P=2 w=4 wynik powinien być 6, Twoj kod daje 1
w = w % 4;
if(w == 0)
{
w = 4;
}
cout << ((int)pow(p%10,w))<< endl;
cout<<((int)pow(p%10,1+(3+w)%4))%10<<endl; ?
(w-1)%4+1.
4+w%4 co do minusu to akurat trzeba pomyśleć, % od liczb ujemnych - zawsze wymaga zastanowienia się.
4+w%4 niepotrzebnie zwiększa wykładniki. O jakich liczbach ujemnych ty piszesz (w>=1)?
Istnieje cykl, trzeba bylo policzyc sobie kilka pierwszych wyników a potem sprawdzić kiedy cykl sie rozpoczyna od nowa. W problemach algorytmicznych trzeba czasami pomyśleć, a nie robić na pałę.
import sys
matrix = [
["1\n","1\n","1\n","1\n"],
["2\n","4\n","8\n","6\n"],
["3\n","9\n","7\n","1\n"],
["4\n","6\n","4\n","6\n"],
["5\n","5\n","5\n","5\n"],
["6\n","6\n","6\n","6\n"],
["7\n","9\n","3\n","1\n"],
["8\n","4\n","2\n","6\n"],
["9\n","1\n","9\n","1\n"],
["0\n","0\n","0\n","0\n"],
]
test_num = int( sys.stdin.readline() )
for test_num in xrange(0, test_num):
input = sys.stdin.readline().split(' ')
sys.stdout.write( matrix[(int(input[0])-1)%10][(int(input[1])-1)%4] )
Albo po prostu
test_num = int(raw_input())
for test_num in xrange(0, test_num):
input = raw_input().split(' ')
a = int(input[0])
b = (int(input[1])-1)%4+1
x = 1
for i in xrange(0, b):
x *= a
x %= 10
print x