【数论】斐波那契数列平方求和

时间：2024-02-24 07:31:25

参考博客：斐波那契数列平方求和的计算公式及其几何证明

斐波那契数列基本的形式：

\huge a_{n}=\left\{\begin{matrix}a_{n-1}+a_{n-2}\ \ \ (n>2) \\ \ \ \ \ \ \ \ \ \1 \ \ \ \ \ \ \ \(n<=2) \end{matrix}\right.

我们要求这个式子：

\large \Sigma a_{n}=1^2+1^2+2^2+3^2+\cdots+a_{n}^2

用几何进行证明：

通过图片可以知道，从图中的左上角进行推导会有：

\LARGE a_{1}^2+a_{2}^2=a_{3}^2

\LARGE a_{1}^2+a_{2}^2=a_{3}*a_{2}

\LARGE a_{1}^2+a_{2}^2+a_{3}^2=a_{2}*a_{3}+a_{3}^2

\LARGE a_{1}^2+a_{2}^2+a_{3}^2=a_{3}(a_{2}+a_{3})

\LARGE a_{1}^2+a_{2}^2+a_{3}^2=a_{3}a_{4}

一直可以进行推导到n项会有：

\large \Sigma a_{n}=1^2+1^2+2^2+3^2+\cdots+a_{n}^2=a_{n}*a_{n+1}

 

 

人类史上最大最好的希望事件

【题意】：

求第i项到第j项之间的面积和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+10;
const int mod=192600817; //质数
ll F[N],sum[N];
void init(){
    F[1]=F[2]=1;
    sum[1]=1;
    sum[2]=2;
    for(int i=3;i<=N;i++){
        F[i]=(F[i-1]+F[i-2])%mod;
        sum[i-1]=(F[i]*F[i-1])%mod;
    }
}
int main()
{
    init();
    int Q;
    while(~scanf("%d",&Q)){
        while(Q--){
            int a,b,c,d,A,B;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            A=max(a*4+b+1,c*4+d+1);
            B=min(a*4+b+1,c*4+d+1);
            ll ans=(sum[A]-sum[B-1]+mod)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

 

相关文章