Wydawałoby się, że jest to temat dość prosty. Mamy liczbę, podnosimy ją do potęgi, bierzemy ostatnią cyfrę i wszystko gra 
No właśnie nie do końca jak się okazuje. Otórz, przy dużych liczbach będziemy mieli problem. Zarówno z wykonaniem obliczenia dla samej operacji potęgowania, jak też potem, dla wybrania ostatniej liczby. Zobaczmy przykład:
KOD 1 - niewydajne wykonanie całego obliczenia
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
number = 1257
power = 1258
r = number ** power # potęgowanie
print(r)
>>OUTPUT:
919981997327433115542827194602138528868089297463863088114311164959164251456466615778871264734746448273209534967
62464304570748498943187158666985598783909015441261311024268389091761177703664294361118153372150099409329922718187
42841113837860772877022111016704272447792840975278188161201441759215670769826161013924507647203697430946635473897
47961591106622587869214230653739734550466665293989807233992825619783218510346660966616629575787345282571338612907
00868588025771478682051462759466326981799623662471714093741149171737089446977406298837268497635531949661642899496
80202150900059192770700584218088858909567313798424950992248366890022101136585806645062895675195287266453150530518
85835501693288916522190812521120660149129525517745543163658608377638723317986019970740520663092642942087271341836
48030083516266256819901793969647464723955557747900592151833331627617161159965354031838707860991553671882441233508
88377841300570249297746106315160507030083766292142979324686524396683778766144862997364840893575698920096591838308
37278505287321011361216910002457655040786751747921658225941366098213176221861974713953295881468146254928310198921
03312948647731428152304350903824246415679669962776976597680429957475262052552425424473250334123388132773715186262
48211949705447591348223065509119071391415407228591011159080419134472248340684518609488945720403205130809901311914
96688043367353529373480750148981509345523322789666162609362845806402486501977264971886552159704780617095319397018
77838819886389562635802800746147133027656650917849962579526178691102426665936097241288599773672460951075165623714
78850852956801086610345612279118845491188756647693401793432012549797383488250191328385993436944319700572340959751
95423633497043694181772069452882304155619533065900531853765337469467996412337389375630768501687701280160480637013
78141287457611531957802412875148988872662952735114956468453181412614018377232612103667679320149011285429332307466
39499046268046167967737340260534661168998147154044281272310067779881358687827457339352013840884192634406292467101
16580779850596398390173672862616882201217965358545693052513053458762501994067415878748573877957994746155301434373
56410737949705508073590104777109372350645898277242963484863402757021309109003276009908852193445142843315985064624
66944456238226752346337538433956084035951311854248340156059437911482692687987846792094775316059875057189787523695
21816728878447650355195235771947492810714895068634312481794860345489724542513854383448558766140184129938838683930
61474595362317997532809660720685802086839318466356402196931232444586992040184039518504101247702980961990132889649
69409045667817301641340231182208908245365283101735870597785496365179270206850834100790363101973396534099566439276
84748749750398289751526154452540836273030830428424813464006304143533365209597258995003470106408545330110390165798
06313914202632628397214246200794009527954580807708494147449797348693947658161212589208846447825053593788255463254
43047719023572234651611689142654545017213388743263995262749265639618057475683476078440589263490695699778566703666
36209236093789140223907854976868269677304091789053380880183697502514392473148710480262078453963493719739320735780
68310385244328909627603028049239560352568406303329271118475356816345724993861906683434902566502740968128256200369
57129326512377867219520865779975469214839613502047905556833957069670535272621066883022377941904043950998365813370
62537681845787858751517886864359032929811849302505829903763703589797872636405350202661000927582322383746799377049
78400982211816750899068522071780068052620361554800427828424901692707739280204799245752644255754276505325507514084
74467898094682515581644770988604006660033047787716920892105836077392657392833406544388816720731501380554860465345
96963945175940294617906033732922636162071086869076860067097008680041658375326356077899719127585886675440684009242
37460028307506841953286225221615014287963877501206202586449
Otrzymaliśmy bardzo długi wynik. Wyświetlmy ostatnią liczbę:
1
2
3
4
print(r[-1::1])
>>po dłuższym czasie
9
To teraz spróbujmy podejścia matematycznego.
Operacje modulo
Moduł z liczby to operacja wyznaczenia reszty z dzielenia np.
2 % 10 = 2
2 / 10 = 0.r => gdzie r oznacza jakąś tam resztę ułamkową
2 - ( 10 * 0 ) = 2 => gdzie zero jest to całkowita liczba z dzielenia 2 / 10
3 % 10 = 3
3 / 10 = 0.r
3 - ( 10 * 0 ) = 3
87 % 16 = 7
87 / 16 = 5.r
87 - ( 5 * 16 ) = 7
Operacje modulo są bardzo przydatne w programowaniu i warto je znać. Dla nas najważniejszą rzeczą na chwilę obecną jest zauważenie faktu, że określając moduł jakiejkolwiek liczby z 10 otrzymamy jej ostatnią cyfrę:
1555 % 10 = 5
12587999877854 % 10 = 4
.
.
.
i tak dalej
Matematyka
To co z tą potęgą? W matematyce jest skrót, aby można było znajdywać ostatnie cyfry wielkich potęg.
Wpierw zobaczmy potęgi dla 3: 3^1 = 3, 3^2 = 9, 3^3 = 27 i 3^4 = 81.
Okazuje się, że ostatnie cyfry są cykliczne i powtarzają się określoną ilość razy. Dla 3 jest to 4 razy, dla 4 jest to 2 razy itd.
Stwórzmy więc tabelkę potęg możliwych cyfr występujących cyklicznie:
| cyfra w podstawie | cyfry występujące cyklicznie |
| 0 | 0 |
| 1 | 1 |
| 2 | 2, 4, 8, 6 |
| 3 | 3, 9, 7, 1 |
| 4 | 4, 6 |
| 5 | 5 |
| 6 | 6 |
| 7 | 7, 9, 3, 1 |
| 8 | 8, 4, 2, 6 |
| 9 | 9, 1 |
Sposób obliczania jest następujący: Obliczmy jaką ostatnią cyfrą będzie dla działania 138^63:
- Ostatnią cyfrą w naszej liczbie jest 8.
- Ósemka ma 4 cyklicznie powtarzające się ostatnie cyfry: 8, 4, 2, 6 - to wynika z naszej tabelki.
- Mamy podnieść do potęgi
63, podzielmy więc liczbę63 moduloprzez ilość możliwych cyfr (w tym wypadku 4), czyli63 % 4 = 3. - 3 cyfrą występującą cyklicznie dla liczby 8 jest 2,
- stąd wniosek, że liczba 2 będzie ostatnią cyfrą w działaniu
138^63.
Sprawdźmy zatem: 138 ^ 63 = 649205877915498822277885239489007892973017747616433644281629
465692684307859636967147601236579562418461601987596488269876226006945103872
I faktycznie, ostatnią cyfrą jest 2.
Tyle z teorii.
Przełóżmy to na kod:
KOD 2 - matematyka i python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
cyclicNumbers = [
[0],
[1],
[2, 4, 8, 6],
[3, 9, 7, 1],
[4, 6],
[5],
[6],
[7, 9, 3, 1],
[8, 4, 2, 6],
[9, 1]
]
number = '138'
power = '63'
arrIndex = int(n[-1::1])
print(cyclicNumbers[arrIndex][int(p) % len(cyclicNumbers[arrIndex]) - 1])
>>>OUTPUT:
2
KOD 3 - Krótki sposób w Python
Mi jednak zależy na ilości znaków, stąd zamiast rozpisywać po kolei obliczenia mogę zapisać wszystko mniej więcej w ten sposób:
1
2
3
4
5
number = 1257
power = 1258
print((number % 10) ** power % 10)
Biorę ostatnią cyfrę z liczby (poprzez % 10), podnoszę ją do wskazanej potęgi i wybieram poprzez % 10 ostatnią cyfrę z liczby. Znacznie wydajniej niż w pierwszej wersji number ** power[-1::1], jednak najwydajniejszy będzie kod nr 2.