Я довольно новичок в программировании, и я наткнулся на этот «простой» вопрос, чтобы вычислить сумму арифметической прогрессии:
Я знаю, что формула выглядит так: (2*a + (n-1)*d) * n/2
a
, d
, n
являются int
, n
может быть около 10000, и a
а также d
может быть до 100000.
Я знаю это, просто написав:
int result = (2*a + (n-1)*d) * n/2;
не будет работать
*Редактировать:
Так что это работает, когда я пишу что-то вроде:
long long result = (2*a+(long long)(n-1)*d)*n/2;
Но просто чтобы уточнить, правильны ли следующие рассуждения:
Из-за (long long)
обертка, (n-1)*d
меняется на тип long long
,
затем (2*a+(long long)(n-1)*d)
становится long long
тоже после добавления? И так идут следующие операции?
Спасибо за прочтение.
Целочисленные типы в C ++ имеют фиксированное количество битов. Точное число варьируется от компьютера к компьютеру, но int
всегда по крайней мере 16 бит, long
не менее 32 бит и long long
составляет не менее 64 бит. Если вы смешаете их, тип результата будет самым длинным. Тем не менее, вы потеряете один бит на знак, если вы не используете соответствующий unsigned
типы.
Итак, в вашем примере у вас есть числа в диапазоне 10 ^ 4 * 10 ^ 5 * 10 ^ 5, так что 10 ^ 14. Это хорошо в диапазоне long long
(~ 10 ^ 19), но не в минимальном диапазоне int
, Сейчас int
часто больше, чем минимум 16 бит, но обычно это только 32 бита. Это объясняет, почему это не сработало для вас.
В этом выражении:
long long result = (2*a+(long long)(n-1)*d)*n/2;
актерский состав (long long)(n-1)
преобразует значение n-1
к long long
(поэтому минимум 64 бита). Это означает, что любая математика, выполненная в связи с этим, также должна быть преобразована в long long
, так d
является long long
, а также n/2
будет долго долго. 2*a
также должен быть преобразован в long long
, Другими словами, все в вашем выражении рассчитывается как 64-битные числа (или потенциально больше в некоторых машинах — не то, что я когда-либо видел одно с большим long long
).
64-разрядное целое число будет легко содержать числа намного больше, чем 10000*100000
(вам понадобится еще 4-5 цифр на каждой стороне, чтобы переполнить 64-битное число), но числа в этом диапазоне могут вызвать переполнение в 32-битной математике, поскольку она больше, чем ~ 2000000000.