Feladatok‎ > ‎

Maradékos gyorshatványozás

ab-t, ahol a és b pozitív egész szám, egyszerűen kiszámolhatjuk egy b tényezős szorzattal (a·a·…·a), de ha b kellően nagy (mondjuk 1000), akkor ez a módszer elég sokáig tart. Viszont gyorshatványozás segítségével kb 10 lépés alatt kiszámolhatjuk az eredményt. Mivel az eredmény ekkora kitevők esetén óriási, ezért modulo m szeretnénk kiszámolni (azaz arra vagyunk kíváncsiak, hogy m-mel osztva mennyi maradékot ad).

Példa

326 ≡ 31·24+1·23+0·22+1·21+0·20 ≡ (324)1·(323)1·(322)0·(321)1·(320) ≡ (324)·(323)·(322)        (mod 7)
320 ≡ 31 ≡ 3                        (mod 7)
321 ≡ (320)(320) ≡ 3·3 ≡ 9 ≡ 2      (mod 7)
322 ≡ (321)(321) ≡ 2·2 ≡ 4 ≡ 4      (mod 7)
323 ≡ (322)(322) ≡ 4·4 ≡ 16 ≡ 2     (mod 7)

Az x≡y (mod m) jelentése, hogy x és y egész számok azonos maradékot adnak m-mel való osztás esetén.

Az algoritmus tehát, hogy a-nak (a példában 3) kiszámoljuk a kettőhatványadik hatványait, és b kettes számrendszerbeli alakjától függően ezek közül a megfelelőket összeszorozzuk

A feladat

Olvasd be a, b és m értékét a standard inputról, és számítsd ki ab értékét modulo m!