Sum of powers (Editorial)

The first two terms of the sum differ from the rest. Let's calculate them separately. Next, we compute the sum in a loop for $i$ from $3$ to $100$, where each term has the form (i - 1) \cdot i^n.

Algorithm implementation

The powmod function computes the value of 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;
}

The main part of the program. Read the input data.

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

Compute the value of res = (1^n + 2^n)~mod~m.

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

Compute the remaining part of the sum.

for (i = 3; i <= 100; i++)
  res = (res + (i - 1) * powmod(i, n, m)) % m;

Print the answer.

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

Python implementation

The myPow function computes the value of 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

The main part of the program. Read the input data.

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

Compute the value of res = (1^n + 2^n)~mod~m.

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

Compute the remaining part of the sum.

for i in range(3, 101):
  res = (res + (i - 1) * myPow(i, n, m)) % m

Print the answer.

print(res)