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]的值要特殊处理 至于为何前面已经讲过了 

下面是代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

15 − 13 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.