Районная олимпиада по информатике. 2008-2009 учебный год.

Задача F. Степень

Ограничение по времени:

2 seconds

Ограничение по памяти:

64 megabytes

Вам даны целые числа $A$, $B$ и $C$. Выведите остаток от деления $A^B$ ($A$ в степени $B$) на $C$. Обратите внимание: $(X · Y) mod Z = ((X mod Z) · (Y mod Z)) mod Z$
$(X + Y) mod Z = ((X mod Z) + (Y mod Z)) mod Z$

Формат входного файла

Единственная строка входного файла содержит 3 целых числа: $A$, $B$, $C$ ($0 <= A, B <= 10^{18}$, $1 <= C <= 10^{18}$). Числа разделены пробелами.

Формат выходного файла

Выходной файл должен содержать одно число – ответ к задаче.

Примеры:

Вход

3 4 5

Ответ

1

Комментарий/решение

#include <iostream>

#include <cmath>

using namespace std;

int main(){

long long a, b, c;

cin >> a >> b >> c ;

long long p = pow(a, b);

cout << p % c;

return 0;

}

в long long p возникнет переполнение. Ответ выйдет неверным.