1210. Very Easy

You are given the value of n and a. Determine the answer for the following series:

Input. Two positive integers n and a.

Output. Print the value of sum. It is known that the result is no more than 10¹⁸.

Sample input	Sample output
3 3	102

SOLUTION

mathematics

Algorithm analysis

The sum should be calculated using a loop. If a ≥ 2, the value n will not be very big, because by problem statement the sum does not exceed 10¹⁸. Separately process the case a = 1, because in this case when using a loop it is possible to get Time Limit. When a = 1, the sum equals to

=

Algorithm realization

Process the case a = 1. The value n * (n + 1) may exceed 10¹⁸, so we shall calculate the sum n * (n + 1) / 2 separately processing even and odd values of n. If n is odd, the sum is calculated by the formula (n + 1) / 2 * n. If n is even, use the formula n / 2 * (n + 1).

if (a == 1)

{

if (n % 2) res = (n + 1) / 2 * n;

else res = n / 2 * (n + 1);

} else

{

res = 0; pow = a;

Find the sum in the variable res using a loop.

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

{

At the i-th iteration, the variable pow contains the value aⁱ. The term i * aⁱ is added to the result res.

res = res + pow * i;

pow = pow * a;

}

}

Print the result.

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

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

long a = con.nextLong();

long res = 0;

if (a == 1)

res = n * (n + 1) / 2;

else

{

long p = a;

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

{

res = res + i * p;

p = p * a;

}

}

System.out.println(res);

con.close();

}

}

Python realization

n, a = map(int,input().split(' '))

s = 0

powa = 1

if a == 1:

s = (1 + n) * n // 2

else:

for i in range(1, n + 1):

powa = powa * a;

s = s + i * powa

print(s)