a216: 數數愛明明

內容 ：
    數數是班上聰明又漂亮的女生，有一天……，她愛上了明明。
她對明明說：「我們的愛，若是錯誤，願你我沒有白白受苦。呃，不是，我們的愛就像是函數！」
    明明說，「是啊，我對妳的愛是與日俱增呢！」
    數數開心地說，「你的意思是，你在第 n 天對我的愛若用函數 f(n) 來描述，那麼，f(n) = n + f(n-1)。也就是說，每一天都比前一天多了一單位的愛，並且與舊的愛累積起來嗎？」
明明點了點頭，然後問，「那麼，妳呢？」
    數數說，「我在第 n 天對你的愛若是 g(n)，那 g(n) = f(n) + g(n-1)！」
於是，明明笑了笑，摟著數數說，我一定會更加愛妳的！
    註：在第一天的時候，f(1) = g(1) = 1。

輸入說明 ：
    輸入以 EOF 結束。每一筆測試資料有一個數字 n，其中 n > 0。
此外，50% 的測資 n <= 500；80% 的測資，n <= 3000；全部的測資 n <= 30000。

輸出說明 ：
    輸出 f(n) 與 g(n)。

範例輸入 ：
1
2
3
5
8
13

範例輸出 ：
1 1
3 4
6 10
15 35
36 120
91 455

程式碼 ：

#include<stdio.h>

int main()
{
    long long n;
    
    while(scanf("%lld",&n)==1)
        printf("%lld %lld\n",(1+n)*n/2,n*(n+1)*(n+2)/6);
    
    return 0;
}

提示 ：

    把遞迴拆開來，會比較好看出公式。

    =======以下是g(n)的推導過程，想自己推的可以忽略，推不出來的可以參考=======

    g(1) = 1

    g(2) =   f(2)  +g(1)

           = (2+1) + (1)
    g(3) =     f(3)    +       g(2)

           =     f(3)    +   (f(2) + g(1)) 

           = (3+2+1) + (2+1) + (1)
    g(4) =       f(4)       +           g(3)
           =       f(4)       +     (f(3)   +       g(2)) 

           =       f(4)       +     f(3)    +  (f(2)  + g(1))

           = (4+3+2+1) + (3+2+1) + (2+1) + (1)

    g(5).....以此類推

    以g(4)為例
    g(4) = 1 + (1+2) + (1+2+3) + (1+2+3+4)
           = 1+1+1+1 + 2+2+2 + 3+3 + 4

           = 1*4 + 2*3 + 3*2 + 4*1

    所以說我們可以找出一個通式 :
    g(n) = 1*n + 2*(n-1) + 3*(n-2) + ... + (n-2)*3 + (n-1)*2 + n*1 

    看到上面這個式子有沒有一種熟悉的感覺，因為那些數學家大大們可以幫我們把這些有規律的東西找到一些很簡單的式子，那就是:

    """ n(n+1)(n+2)/6 """

    PS:公式怎麼來的請看這裡

    ===================================================================

http://zerojudge.tw/ShowProblem?problemid=a216