913 - Joana and the Odd Numbers

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?

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

出處: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=854

---

這一題題目是給您其中某一列奇數的數目，接著要您求出這一列最後三個奇數的總和。如果這一題用暴力解法應該會超過time limit，因為測試資料的範圍是1<N<1000000000，所以此題不能用暴力解。可以先思考一下題目要您求出的答案是"某一奇數列的最後三個數字的總和"，所以其實只要知道這三個數字的其中一個數字就好了，因為其他兩個數字可以推淂。既然如此我們可以選擇先求最後一個數字，因為最後一個數字比較好從規律推到，可以觀察一下題目的規律來推出最後一個數字:

若輸入為3, 最後一個數字為:

1 + 3 * 2 = 7

則三數總和為:

3 + 5 + 7 = 15

若輸入為5, 最後一個數字為:

1 + 3 * 2 + 5 * 2 = 17

則三數總和為:

17 + 15 + 13 = 45

.

.

.

若輸入為n, 最後一個數字為:

1 + 3 * 2 + 5 * 2  + ... + n * 2 = a

則三數總和為:

a + a - 2 + a - 4 = 3 * a - 6

至於1 + 3 * 2 + 5 * 2  + ... + n * 2 = a這個算式可以簡化成以下式子:

1 + 2 * (3 + 5 + ... + n) = a

而括弧裡面的式子就是等差級數，所以利用等差級數公式代掉後變成以下算式:

1 + 2 * (3 + n) * (n - 1) / 2 / 2

整理一下可以變成此式:

(n ^ 2 + 2 * n - 1) / 2 = a

最後再把a代入3 * a - 6就變成以下式子:

3 * (n ^ 2 + 2 * n - 1) / 2 - 6

接著可以簡化成

3 * (n ^ 2 + 2 * n - 5) / 2

這就是最終公式，把input代入即可求解。還有一個要注意的是若資料型態用int會容納不下最終解，所以必須要用更大的資料型態來儲存。

以下是c++ code:

#include <iostream>
using namespace std;

int main() {
    long long n;

    while (cin >> n)
        cout << 3 * (n * n + 2 * n - 5) / 2  << endl;

    return 0;
}