数论整理
特殊数方面：
p.s. ：黄金分割0.6180339887
①斐波那契数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368（等于将杨辉三角同一斜行的数加起来）
eg:兔子生孩子的增长方式 F(n) = F(n - 1)+F(n - 2)
通项公式
特性：平方与前后项：从第二项开始，每个偶数项的平方都比前后两项之积少1，每个奇数项的平方和都比前后两项之积多1
应用：
one：矩形面积：前几项的平方和可以看成不同大小的正方形，由于斐波那契的递推公式可以拼成大的矩形。
得恒等式：
two：每3个连续的数中有且只有一个被2整除，
每4个连续的数中有且只有一个被3整除，
每5个连续的数中有且只有一个被5整除，
每6个连续的数中有且只有一个被8整除，
每7个连续的数中有且只有一个被13整除，
每8个连续的数中有且只有一个被21整除，
每9个连续的数中有且只有一个被34整除，
three：尾数循环个位数是60步的循环，进一步，斐波那契数列的最后两位数是一个300步的循环，最后三位数是一个1500步的循环，最后四位数是一个15000步的循环，最后五位数是一个150000步的循环。
拓拓拓拓：
斐波那契–卢卡斯数列：如1，4，5，9，14，23…，因为1，4开头，可记作F[1，4]，斐波那契数列就是F[1，1]，卢卡斯数列就是F[1，3]，斐波那契—卢卡斯数列就是F[a，b]。
eg：1 3 4 7 11 18……卢卡斯数列的通项公式为 f(n)=[(1+√5)/2] ^ n+[(1-√5)/2] ^ n
特殊联系：F(n)*L(n)=F(2n)，及L(n)=F(n-1)+F(n+1)
任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列。如：F[1,4]n+F[1,3]n=F[2,7]n，F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1），F[1，4]数列：|4 * 4-1 * 5|=11
任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得。中间项的平方数与前后两项之积的差的绝对值是一个恒值。
f(n) = f(n-1) * p + f(n-2) * q，称为广义斐波那契数列。
当p=1，q=2时，我们得到佩尔—勾股弦数（跟边长为整数的直角三角形有关的数列集合）。
当p=2，q=-1时，我们得到等差数列。其中f1=1，f2=2时，我们得到自然数列1，2，3，4…。自然数列的特征就是每个数的平方与前后两数之积的差为1（等差数列的这种差值称为自然特征）。
//递归算法优化 # include <iostream> # include <cstdio> # define MAX (101) using namespace std; int a[MAX]; int f(int n){ if(a[n]!=-1) return a[n]; else{ a[n]=f(n-1)+f(n-2); return a[n]; } } int main(){ int n; cin>>n; for(int i=0;i<=MAX-1;i++){ //初始化 a[i]=-1; } a[0]=0;a[1]=1; printf("%d",f(n)); return 0; } //高精度计算 char sum[1200]; int s=0,m=0,n; int main() { cin>>n; string s1,s2; int a[1200],b[1200]; int he,i; s1="0"; s2="1"; for(m=2;m<n;m++) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); a[0]=s1.length(); for(i=1;i<=a[0];i++) { a[i]=s1[a[0]-i]-'0'; } b[0]=s2.length(); for(i=1;i<=b[0];i++) { b[i]=s2[b[0]-i]-'0'; } he=(a[0]>b[0]?a[0]:b[0]); for(i=1;i<=he;i++) { a[i]+=b[i]; a[i+1]+=a[i]/10; a[i]%=10; } he++; while((a[he]==0)&&(he>1)) he--; for(i=he,s=0;i>=1;i--,s++) { sum[s]=a[i]+'0'; } s1=s2; s2=sum; } cout<<s2<<endl; return 0; }
