Browsed by
分类: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 is an integer T indicating the number of test cases.

For each test case, there are 3 integers K (1 ≤ K ≤ 106), X (3 ≤ X ≤ 100) and M (10 ≤ M ≤ 106), which are defined in above description.

Output

For each test case, please output the corresponding (S[n] ÷ X) mod M.

Sample Input

culate Prime S
Sample Output 

解决这个问题需要的知识储备为 :

  1. Fibonacci数列的性质
  2. 矩阵快速幂计算Fibonacci
  3. 取模运算的性质 (a/b)%c=(a%b*c)/b

在这里有Fibonacci数列的基本性质 ,   快速幂的知识在这里有,矩阵快速幂的代码在下面 ,理解了快速幂之后很好理解 。

本题首先要读清题目,本题涉及的元素较多 ,滤清思路之后 本题要求的 是 不小于 第 K 个 Prime S 的能被X整除的S 序列里的数字 ,而经过我们小数据打表发现 S序列为Fibonacci数列从第三项开始 也就是 2 3 5 8 13 … 而 Prime S 为 Fibonacci数列里的素数 ,由Fibonacci的性质知,Fibonacci中 第n项为Fibonacci素数的条件是 n为质数 当 n>=5时成立  ,所以我们可以通过这个性质 结合素数表 来获得 第 K个Fibonacci素数在Fibonacci数列里的下标  在代码的注释里有具体例子 。然后 我们就可以往后枚举这个下标 用 矩阵快速幂的方法来求第n个Fibonacci数 ,然后找到能被X整除的 ,并进行 S/X %C = (S%XC)/X 的运算把结果输出即可 由于我的素数生成函数(筛法)把count的初值设置错误 导致开始一直在错, 另外需要注意 p[1] 和 p[2]的值要特殊处理 至于为何前面已经讲过了 

下面是代码