Description
You only need to solve up to 6/8 accepted.
The last two testcases are left as an exercise since it requires a minor optimization. (These two NOT be covered in the midterm exam.)
elfnt has many Cinnamorolls, and he wants to choose four of them to decorate his room depending on today’s happy value $n$.
Each Cinnamoroll has a size number, and elfnt possesses all different sizes of Cinnamorolls, with four of each size.
The happy value is calculated as $a \times b \times c + d$. elfnt wants to know how many ways are there to choose the Cinnamorolls when today's happy value is $n$.
Formally, find the number of quadruples $(a, b, c, d)$ of positive integers such that:
$$ a \times b \times c + d = n $$
Input
A single integer $n$.
Constraints
$2 \leq n \leq 5 \cdot 10^7$
Subtask
- (Testcase 1) $2 \leq n \leq 50$
- (Testcase 2) $2 \leq n \leq 100$
- (Testcase 3) $2 \leq n \leq 1000$
- (Testcases 4-6) $2 \leq n \leq 10^6$
- (Testcase 7) $2 \leq n \leq 5 \cdot 10^6$
- (Testcase 8) No additional constraints.
Output
Print the number of quadruples $(a, b, c, d)$ of positive integers satisfying the condition and followed by a new line.
Hint
When $n = 4$, all valid quadruples $(a,b,c,d)$ are:
$$ (1,1,1,3),\; (1,1,2,2),\; (1,1,3,1),\; (1,2,1,2),\; (2,1,1,2),\; (1,3,1,1),\; (3,1,1,1) $$ Hence, there are $7$ valid quadruples in total.