1210. Очень просто

По заданным числам n и a вычислить значение суммы

Вход. Содержит два натуральных числа n и a.

Выход. Вывести целое число, являющееся значением указанной суммы. Известно, что выводимая сумма не больше 10¹⁸.

Пример входа	Пример выхода
3 3	102

РЕШЕНИЕ

математика

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

Следует вычислить указанную сумму при помощи цикла. Если a ≥ 2, то значение n не будет слишком большим, так как по условию задачи искомая сумма не превосходит 10¹⁸. Отдельно следует обработать a = 1, так как в этом случае при вычислении циклом можно поучить Time Limit. При a = 1 сумма равна

=

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

Обрабатываем случай a = 1. Значение n * (n + 1) может превосходить 10¹⁸, поэтому вычислять значение n * (n + 1) / 2 будем отдельно для четного и нечетного числа n. Если n нечетно, то сумма вычисляется по формуле (n + 1) / 2 * n. Если n четно, то по формуле 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;

Вычисляем сумму в переменной res при помощи цикла.

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

{

На i-ой итерации переменная pow содержит значение aⁱ. К результату res добавляется i * aⁱ.

res = res + pow * i;

pow = pow * a;

}

}

Выводим результат.

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

Java реализация

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 реализация

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)