Problem Statement: Given an integer $$$ n $$$, find the sum of $$$ f(k) $$$, where $$$ f(k) = 1 + 2 + 3 + \ldots + k $$$ and $$$ 1 <= k <= n $$$ . Output the result modulo $$$ 10^9 + 7 $$$. max(n) = $$$10^9$$$.
MY approach: Firstly , very very sorry for my poor english. My approach was to use the formula n(n + 1)/2 in a loop. But I am getting TLE every time. But I don't know how to fix it any further. I first I used 2 nested loops and then only one loop. But not working.
Can some generous person help me?
Auto comment: topic has been updated by Surgeon_of_Hell (previous revision, new revision, compare).
Ok so we're summing this
which is
The sum of
and
so now the sum is
this runs in constant time
some stress test for $k=100$
What is stress test budyy? (exp: haha) Just kidding...
It's how you check if your optimized solution works as the naive one
like proof by AC
Basically, there is a $$$O(1)$$$ solution for this problem. You can convert the problem into the following equation: 1 + (1 + 2) + (1 + 2 + 3) + ... + (1 + 2 + ... + n). Then, solve the equation like this:
And lastly, you must use long long data type instead of int because there are many $$$n^2$$$ terms in the resultant equation.
https://usaco.guide/adv/line-container?lang=cpp#half-plane-intersection it should become clear after this.