Browsed by
Category: Number Theory

[转]Fibonacci 数列的基本性质

[转]Fibonacci 数列的基本性质

fibonacci数列的性质: 1.gcd(fib(n),fib(m))=fib(gcd(n,m)) 证明:可以通过反证法先证fibonacci数列的任意相邻两项一定互素,然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m)),递归可 求gcd(fib(n),fib(m))=gcd(fib(k),fib(l)),最后k=l,不然继续递归。K是通过展转相减法求出,易证k=gcd(n,m),所以gcd(fib(n),fib(m)) =fib(gcd(n,m))。   2.如果fib(k)能被x整除,则fib(k*i)都可以被x整除。 3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1 4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n) 5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1 6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1) 7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1 8.f(n+m)=f(n+1)·f(m)+f(n)*f(m-1) 9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1) 10.f(2n-1)=[f(n)]^2-[f(n-2)]^2 11.3f(n)=f(n+2)+f(n-2) 12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

ZOJ 3707 Calculate Prime S 矩阵快速幂+Fibonacci的性质

Calculate Prime S Time Limit: 2000MS Memory Limit: 262144KB 64bit IO Format: %lld & %llu Description Define S[n] as the number of subsets of {1, 2, …, n} that contain no consecutive integers. For each S[n], if for all i (1 ≤ i < n) gcd(S[i], S[n]) is 1, we call that S[n] as a Prime S. Additionally, S[1] is also a Prime S. For the Kth minimum Prime S, we’d like to find the minimum S[n]which is multiple of X and not less than the Kth minimum Prime S. Please tell us the corresponding (S[n] ÷ X) mod M. Input There are multiple test cases. The first line of input…

Read More Read More