Сума степенів#9644

Сума степенів (Розбір)

Перші два доданка суми відрізняються від інших. Обчислимо їх окремо. Далі рахуємо суму в циклі по $i$ від $3$ до $100$ , кожен доданок має вигляд $(i - 1) \cdot i^{n}$ (i - 1) \cdot i^n.

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

Функція powmod обчислює значення $x^{n} m o d m$ x^n~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);

Обчислюємо $r es = (1^{n} + 2^{n}) m o d m$ res = (1^n + 2^n)~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^{n} m o d m$ x^n~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())

Обчислюємо $r es = (1^{n} + 2^{n}) m o d m$ res = (1^n + 2^n)~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)