MegaSum
SRM 454 · 2009-12-05 · by Gluk
SRM 454 · 2009-12-05 · by Gluk · Math
Problem Statement
Problem Statement
Let us define an infinite table of integers as follows:
Each cell is uniquely identified by the value it contains. Let us define S(X) as the sum of all the values in the rectangle with cell 1 as its upper-left corner and cell X as its lower-right corner. For example, S(12) is the sum of all the values in the green rectangle shown above.
You are given along N. First, find the rectangle with cell 1 as its upper-left corner and cell N as its lower-right corner. Then, calculate the sum of S(X) for all values X inside this rectangle. Return this sum modulo 1,000,000,007.
For example, if N is 8, you would first find the 3 x 2 rectangle with 1 in its upper-left corner and 8 in its lower-right corner. You would then calculate S(X) for each value X in this rectangle: S(1) = 1, S(2) = 3, S(9) = 12, S(4) = 5, S(3) = 10, and S(8) = 27. You would them sum these values to get 1 + 3 + 12 + 5 + 10 + 27 = 58.
Each cell is uniquely identified by the value it contains. Let us define S(X) as the sum of all the values in the rectangle with cell 1 as its upper-left corner and cell X as its lower-right corner. For example, S(12) is the sum of all the values in the green rectangle shown above.
You are given a
For example, if N is 8, you would first find the 3 x 2 rectangle with 1 in its upper-left corner and 8 in its lower-right corner. You would then calculate S(X) for each value X in this rectangle: S(1) = 1, S(2) = 3, S(9) = 12, S(4) = 5, S(3) = 10, and S(8) = 27. You would them sum these values to get 1 + 3 + 12 + 5 + 10 + 27 = 58.
Constraints
- N will be between 1 and 10^10, inclusive.
Examples
0)
8 Returns: 58
This is the example from the problem statement.
1)
12 Returns: 282
2)
11 Returns: 128
3)
6 Returns: 50
4)
34539 Returns: 437909839
Submissions are judged against all 164 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MegaSum with a public method int calculate(long long N) · 164 test cases · 2 s / 256 MB per case