[C++] spoj.pl: "Potęgowanie"

Psycho · Post autor: **Psycho** » 12 maja 2009, o 22:17

Robiłem sobie to zadanie ():

542. Potęgowanie
Kod zadania: T_POTEGA

Oblicz:

Xn mod p
Wejście

t - Liczba testów

W oddzielnych liniach kolejne testy w formacie:
x n p,

gdzie x,n,p są liczbami całkowitymi takimi, że 1<=x<=100, 0<=n<=10000, 2<=p<=100.
Wyjście

W oddzielnych liniach dla każdego testu jedna liczba:
y

taka, że 0<=y<=p-1 i istnieje liczba całkowita m taka, że Xn = pm+y

i w końcu jak napisałem "poprawny" kod, zobaczyłem, że tam w ostatniej linijce trzeba obliczyć resztę z dzielenia \(\displaystyle{ 81^{9345}}\) przez 75. I tu moje pytanie, czy zna ktoś algorytm, dzięki któremu można taką resztę znaleźć?

spajder · Post autor: **spajder** » 12 maja 2009, o 22:25

a policz najpierw \(\displaystyle{ 81\pmod{75}}\)

Psycho · Post autor: **Psycho** » 12 maja 2009, o 22:41

No to jest oczywiste, ale mogę np. potrzebować kilka razy zastosować kongruencje (w tym wypadku \(\displaystyle{ 6^{9345}}\) wciąż nie mieści się long double) dlatego szukam algorytmu . Heh, jak to pisałem to pomyślałem, że może nie jest to takie trudne

spajder · Post autor: **spajder** » 12 maja 2009, o 22:43

Nie podnoś do potęgi. Najłatwiejszy algorytm operuje po prostu na resztach z dzielenia i nie powoduje przekroczenia zakresu:

Kod: Zaznacz cały

int reszta = 1;
for(int i = 0; i < 9345; i++)
    reszta = (reszta*6)%75;

Psycho · Post autor: **Psycho** » 13 maja 2009, o 08:02

O to chodziło, dzięki!