http://acm.cist.bnu.edu.cn/contest/problem_show.php?pid=4058

description

ZY最近遇到了一种奇妙的数，这种数可以表示成1 + 2 + 3 + ... + n的和，若每个数代表若干个小球，则将这些小球堆起来，就成了一个三角形(如图)

*

* *

* * *

* * * *

所以这种数被称为是三角数，ZY惊奇地发现任意两个连续的三角数之和是一个平方数，但他还想知道是否三角数本身就可以是一个平方数，于是他苦思冥想，终于找到了几个三角平方数，问题是这样的数存在无限多个吗？于是他又去请教FYJ大牛，FYJ大牛瞬间就秒杀了这个问题，得出了肯定的回答，为了一同膜拜FYJ大牛，ZY请你帮忙编写一个程序，给定输入k,输出第k个三角平方数所对应的平方数

例如,第3个三角平方数为 s = 1 + 2 + 3 + ... + 49 = 1225 = 352.

这题关于 pell数 佩尔数

1    =  1  × 1

6    =  2  × 3

35   =  5  × 7

204  =  12 × 17

可以在右边的两列数中都推出如下的递推式：

P(0)=0

P(1)=1

P(n)=2*P(n-1)+P(n-2)

这个数列被称为是佩尔数，它可以写成如下形式：

((P(k+1)+P(k))*P(k))^2=((P(k-1)+P(k))^2*((P(k-1)+P(k))^2-(-1)^k))/2

附递推代码：

#include <stdio.h>

int main()

{

   int T, k, i, x1, x2;

   scanf("%d", &T);

   while(T--) {

      scanf("%d", &k);

      x1 = 1, x2 = 1;//x1是第一列 x2是第二列

      for(i = 1; i < k; ++i) {

         x2 = 2 * x1 + x2;

         x1 = x2 - x1;

      }

      printf("%d\n", x1 * x2);

   }

   return 0;

}

ps1:关于pell数很好的一篇论文

http://wapedia.mobi/zh/%E4%BD%A9%E5%B0%94%E6%95%B0?t=2.

ps1:几个有名的两项递推数列：

费波那契数:0、 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987、 1597、 2584、 4141、 6765等。

卢卡斯数 (Lucas Number):2、 1、 3、 4、 7、 11、18、 29、 47、 76、 123、 199、 322、 521、 843、 1364、 2207、 3571、 5781、 9349 等

佩尔数 (Pell Number):0、 1、 2、 5、 12、 29、 70、 169、 408、 985、 2378、 5741等。

佩尔 - 卢卡斯数 (Pell - Lucas Number) :2、 2、 6、 14、 34、 82、 198、 478、 1154、 2786、 6726等。

其实都是 卢卡斯数列 (Lucas Sequence) 的特殊形式，详见http://baike.baidu.com/view/1327998