9644. Сумма степеней

Найдите значение суммы

(1ⁿ + 2ⁿ + 2 * 3ⁿ + 3 * 4ⁿ + 4 * 5ⁿ + .... + 99 * 100ⁿ) mod m

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

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

Пример входа	Пример выхода
12345678 35242346	5447885

РЕШЕНИЕ

степень

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

Первые два слагаемых суммы отличаются от остальных. Вычислим их отдельно. Далее считаем сумму в цикле по i от 3 до 100, каждое слагаемое имеет вид (i – 1) * 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);

Вычисляем res = (1ⁿ + 2ⁿ) mod m.

res = (powmod(1, n, m) + powmod(2, n, m)) % m;

Находим остальную часть суммы.

for (i = 3; i <= 100; i++)

res = (res + (i - 1) * powmod(i, n, m)) % m;

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

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

Python реализация

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

def myPow(x, n, m):

if n == 0: return 1

if n % 2 == 0: return myPow((x * x) % m, n / 2, m)

return (x * myPow(x, n - 1, m)) % m

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

n, m = map(int, input().split())

Вычисляем res = (1ⁿ + 2ⁿ) mod m.

res = (myPow(1, n, m) + myPow(2, n, m)) % m

Находим остальную часть суммы.

for i in range(3, 101):

res = (res + (i - 1) * myPow(i, n, m)) % m

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

print(res)