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 263.
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)2 / 4。
再來,從題目可以知道,這個數列的第 k 個數字之值為 2k - 1,將剛剛得出的結果減 1(因為我們要的是倒數第二個數字) 代入 k,就可以得到此數字為 2 * {[(N + 1)2 / 4] - 1} = [(N + 1)2 / 2] - 3。接著再將這個數字乘以 3 就得到題目要的結果了。
需要特別注意的一點是,由於數字相當大,因此這裡的整數要宣告成 "long long"。不過這個 "long long" 我之前完全沒看過,查了一下 Wikipedia,看起來是 64 位元新增的資料型態,支援的數字範圍為 -264 - 1 ~ 264 - 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; }
2 回覆:
#include多了一個>
感謝, 已修正
張貼留言