Codeforces 268b - Неизвестное значение в качестве выхода для этих небольших C++ программы

Question

Здесь C++ код для Codeforces problem Я пытаюсь решить:

#include <iostream> 

using namespace std; 

int main() 
{ 
    int n = -1; 
    unsigned long long possible_combinations = 0; 

    cin >> n; 

    possible_combinations = (((n - 1) * n * (n + 1))/6) + n; 
    cout << possible_combinations; 

    return 0; 
} 

где 1 <= n <= 2000.

Он вычисляет правильное значение для малых значений n, но когда я использую 2000, он показывает - 18446744073611230851. Я пробовал только несколько тестовых случаев.

Я знаю, что формула правильная, и программа должна давать 1333335000 как выход, но это не так. В чем проблема с кодом?

Answer 1

Попробуйте это:

possible_combinations = (((unsigned long long) (n - 1) * n * (n + 1))/6) + n; 

Причина проблемы проста: (n - 1) * n * (n + 1) является слишком большой для int если n==2000 (но ваш n является int, так что это выражение возвращает int). Таким образом, вы можете попросить компилятор использовать больший тип (язык не может автоматически расширять шрифт) или просто изменить тип n (используйте unsigned long longn = -1; вместо int n = -1;).

Answer 2

Когда вы выполняете арифметику, результат не продвигается до более широкого типа, если он становится слишком большим.
Поскольку n является int и 1 и 6 являются int с, весь расчет делается с int.

1999 * 2000 * 2001 такой большой - 7,999,998,000 - это переполнение int.

Использовать unsigned long long по всему миру.