9644. Sum of powers

Find the value of the sum

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

Input. Two positive integers n and m (n, m ≤ 10⁸).

Output. Print the value of the sum modulo m.

Sample input	Sample output
12345678 35242346	5447885

SOLUTION

exponentiation

Algorithm analysis

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) * iⁿ.

Algorithm realization

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

}

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

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

Compute the value of res = (1ⁿ + 2ⁿ) 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 realization

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

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

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

Compute the value of res = (1ⁿ + 2ⁿ) 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)