9646. Сумма степеней 2

Найдите значение суммы (1¹ + 2² + 3³ + .... + nⁿ) mod m.

Вход. Два натуральных числа n и m (n, m ≤ 10⁶).

Выход. Выведите значение суммы по модулю m.

Пример входа	Пример выхода
4 100	88

РЕШЕНИЕ

степень

Анализ алгоритма

Вычислим указанную сумму при помощи цикла. Значения степеней iⁱ вычисляем за время O(i).

Реализация алгоритма

Функция powmod вычисляет значение xⁿ mod m.

long long powmod(long long x, long long n, long long m)

{

if (n == 0) return 1;

if (n % 2 == 0) return powmod((x * x) % m, n / 2, m);

return (x * powmod(x, n - 1, m)) % m;

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld", &n, &m);

Вычисляем указанную сумму.

for (i = 1; i <= n; i++)

res = (res + powmod(i, i, m)) % m;

Выводим ответ.

printf("%lld\n", res);