【解題】Joana and the Odd Numbers

ACM Volume IX 913 - Joana and the Odd Numbers


Background

Joana loves playing with odd numbers. In the other day, she started writing, in each line, an odd number of odd numbers. It looked as follows:

1
3 5 7
9 11 13 15 17
19 21 23 25 27 29 31
...

On a certain line Joana wrote 55 odd numbers. Can you discover the sum of the last three numbers written in that line? Can you do this more generally for a given quantity of odd numbers?


The Problem

Given the number N of odd numbers in a certain line, your task is to determine the sum of the last three numbers of that line.


Input

The input is a sequence of lines, one odd number N (1 < N < 1000000000) per line.


Output

For each input line write the sum of the last three odd numbers written by Joana in that line with N numbers. This sum is guaranteed to be less than 2⁶³.


Sample Input

3
5
7


Sample Output

15
45
87


解題思考

　　這題與其說是考程式設計，不如說是考數學。

　　首先，題目要的是某行的最後 3 個數字和，我們可以直接當作該行倒數第 2 個數字乘以 3。

　　至於這個數字該怎麼得到呢？我們需要先知道的是他是從 1 開始的第幾個數字。從題目可以知道，數列的第 k 行有 2k - 1 個數字。因此，當某列有 N 個數字時，該列的最後一個數字是第幾個數字可由等差級數和求得：{(N + 1) * [(N + 1) / 2]} / 2 = (N + 1)² / 4。

　　再來，從題目可以知道，這個數列的第 k 個數字之值為 2k - 1，將剛剛得出的結果減 1(因為我們要的是倒數第二個數字) 代入 k，就可以得到此數字為 2 * {[(N + 1)² / 4] - 1} = [(N + 1)² / 2] - 3。接著再將這個數字乘以 3 就得到題目要的結果了。

　　需要特別注意的一點是，由於數字相當大，因此這裡的整數要宣告成 "long long"。不過這個 "long long" 我之前完全沒看過，查了一下 Wikipedia，看起來是 64 位元新增的資料型態，支援的數字範圍為 -2^{64 - 1} ~ 2^{64 - 1} - 1。Well，相當神奇。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    // 注意, 這裡要宣告成 "long long"
    long long n;
    while (cin >> n)
    {
        cout << 3 * ((n + 1) * (n + 1) / 2 - 3) << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif

    return 0;
}