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