Numbers With Equal Remainder and Quotient

Interview

Time limit2sMemory limit256 MB

Summary
Given N, find the sum of all positive integers x whose quotient and remainder are equal when divided by N.
Level

Easy2 of 10

Topics
Math
Solved
No attempts yet

Problem

A positive integer N is given. Call a positive integer x valid if, when x is divided by N, its quotient and remainder are equal.

Find the sum of all valid positive integers x.

Input

The first line contains a positive integer N not greater than 2,000,000.

Output

Output the sum of all valid positive integers.

Examples2

  1. Example 1

    Input
    3
    Expected output
    12

  2. Example 2

    Input
    2000000
    Expected output
    3999999999999000000