牛客网 NC18264 斐波那契

题意

设$f_i$表示斐波那契数的第i项

求

$$f_{n-1} \times f_{n+1} - f_{n}^2$$

$ 2 \leq n \leq 10^{1000000} $

题解

推一下简单的式子

$$\begin{equation} \begin{aligned} &f_{n-1}f_{n+1} - f{n}^2 \\ &= f_{n-1}f_{n+1}-f_{n-1}^2-2f_{n-1}f_{n-2}-f_{n-2}^2 \\ &=f_{n-1}f_{n}-2f_{n-1}f_{n-2}-f_{n-2}^2 \\ &=f_{n-1}^2-f_{n-1}f_{n-2}-f_{n-2}^2 \\ &=f_{n}(f_{n-1}-f_{n-2})-f_{n-1}f_{n-2} \\ &=f_{n}f_{n-3}-f_{n-1}f_{n-2} \\ &=f_{n-1}f_{n-3}+f_{n-2}f_{n-3}-f_{n-1}f_{n-2} \\ &=f_{n-1}f_{n-3}-f_{n-2}^2 \end{aligned} \end{equation}$$

所以有

$$f_{n-1}f_{n+1}-f_{n}^2=f_{n-3}f_{n-1}-f_{n-2}^2$$

所以每两项相同

代码

 #include <cstdio>
using namespace std;
int main(){
    char c;
    int num=0;
    c=getchar();
    while(!(c>='0'&&c<='9')){
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        num=(num*10%2+c-'0')%2;
        c=getchar();
    }
    if(num==0)
        printf("1\n");
    else
        printf("-1\n");
    return 0;
}