Сумма чисел от 1 до n. C++

Question

Здесь

Найти сумму от 1 до n.

Вот мой код:

#include <iostream>
using namespace std;

int main()
{
    int n, sum = 0;
    cin >> n;

    if (n<=-1) for(int i=1; i>=n; i--) sum+= i; // сума отрицательных
    else sum = (1+n) * n / 2; // по формуле

    cout << sum;
}

Скорее всего, программа не проходит по времени. Посоветуйте алгоритм пожалуйста. В чем подвох этой задачи?

Answer 1

Ваши главные ошибки - во-первых, вы не учитываете, что сумма может быть на все 64 бита... Соответственно, суммировать циклом - это кошмарное решение.

Нельзя даже множить n*(n+1)/2 - потому что можно получить переполнение!

Нужно, например, вот так:

#include <iostream>
#include <iomanip>

using namespace std;


int main(int argc, const char * argv[])
{
    long long n;
    cin >> n;
    if (n > 0)
    {
        if (n%2)
            n = ((n+1) >> 1)*n;
        else
            n = (n >> 1)*(n+1);
    }
    else if (n==0) n = 1;
    else
    {
        n = -n;
        if (n%2)
            n = ((n+1) >> 1)*n;
        else
            n = (n >> 1)*(n+1);
        n = 1 - n;
    }
    cout << n << endl;

}