首页 > 代码库 > 1005:取余,循环,找规律

1005:取余,循环,找规律

Problem Description
A number sequence is defined as follows:
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A, B, and n, you are to calculate the value of f(n).
 
Input
The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.
 
Output
For each test case, print the value of f(n) on a single line.
 
Sample Input
1 1 3
1 2 10
0 0 0
 
Sample Output
2
5

1.必然会出现循环

这是基于下面事实(*不太懂*):

1. R(n+2)=F(n+2) mod P=(F(n+1)+F(n)) mod P=(F(n+1) mod p +F(n) modp) mod p

2. 斐波那契数列的最大公约数定理:gcd(F(m),F(n))=F(gcd(m,n))
最大公约数定理表明如果F(k)能被N整除,则F(ik)也能被N整除,这就表明了斐波那契数列所含因子的周期性,下面列举:
因子:2,3,4,5, 6,7,8, 9,10,11,12
周期:3,4,6,5,12,8,6,12,15,10,12
我们称所生成的序列为剩余序列,那么一旦出现某个F(k) 能被N整除(这需证明我的一个猜想:对于任意素数P,F(P),F(P-1)和F(P+1)三个中定有一个能被P整除),以后F(ik)都能被N整除,亦即剩余序列周期地出现0,下一个剩余序列值为N-1种可能,总会重复,有两个相邻的重复该序列就一定重复,亦即具有周期性。
这个周期叫做皮萨诺周期
 
2.正确思路
因为mod7的关系,而且f(1)=f(2)=1,所以f(n)的值是循环分布的,而且一定会回到f(n-1)=f(n)=1。
 
并且还可以得出,这个循环不大于49,因为相邻连个f只有7种取值,这样f(n-1)和f(n)共有49种组合。
所以,只要找出循环因子即可,寻找方法正是根据f(n-1)=f(n)再次出现的地方来计算。
可以首先为这个题目写一个测试程序,设定一个a b n(n比较小时)的值,看看输出规律。
 
只要找到k使得f(k-1) = f(n-1),f(k-2)=f(n-2);特别地,当k等于2时就可以了,因为f(1),f(2)是循环的开始。
又因为f(n-1),f(n-2)都只能取0到6共7个数,因此有49种组合方式,也就是说50内必然可以找到满足条件的k,就是循环周期小于50。
 
3.解题思路:

1.n的数值很大,这类数值很大的问题一般都有规律,找出循环节(周期)是关键;

2.找规律,这道题是从 f(1) = 1 和 f(2) = 1 开始,然后依次模7,可知 f(n) 只有7种情况,所以两数相邻只有7*7=49种;

3.所以从 f(1) 到 f(49) 必会出现相邻两个 f(m-1) = 1 , f(m) = 1,所以 f(n) 为周期函数,49为其一个周期。

 

3.实现代码:

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int A,B;
 5 
 6 int f(int n)
 7 {
 8     if(n==1||n==2)
 9         return 1;
10     else{
11          return ((A * f(n - 1) + B * f(n - 2)) % 7);
12 
13     }
14 }
15 
16 int main()
17 {
18     long long n;
19     while(1)
20     {
21         cin>>A;
22         cin>>B;
23         cin>>n;
24         if(A==0 && B==0 && n==0)
25             break;
26         else
27         {
28             n %= 49;
29             cout<<f(n)<<endl;
30         }
31     }
32     return 0;
33 }

 

1005:取余,循环,找规律