【杭电ACM小弟想知道为什么循环周期是49呢,Anumbersequenceisdefinedasfollows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.GivenA,B,andn,youaretocalculatethevalueoff(n).InputTheinputconsistsofmultiplet】
1人问答
问题描述：
杭电ACM
小弟想知道为什么循环周期是49呢,
Anumbersequenceisdefinedasfollows:
f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.
GivenA,B,andn,youaretocalculatethevalueoff(n).
Input
Theinputconsistsofmultipletestcases.Eachtestcasecontains3integersA,Bandnonasingleline(1
井海明回答：
首先这是一个数列,也就是一系列的数,这个是句废话,但是必须得说
其次,除了f1和f2以外,每个数字都由前两个数字决定,这个是公式确定的
也就是说,如果对于数列f1f2..fafb.fcfd存在fa=fc且fd=fb那么后续的一定循环
第三,对于任意的fn,由于是mod7所以其取值只能是0123456这7种可能
这样对于任意的连续两个数字,fafb,可能的组合就是7*7=49种,而实际上,0,0序列是一个特殊的情况,除非AB都是7的倍数,那么所有序列都是0,不然是不会出现00的可能的.
所以,如果提取一个长为50的任意子序列,可以提取出49个连续对,这49个中肯定会有至少一个重复,也就是循环周期了
这个循环周期
其它推荐
其它推荐
最新更新
精品分类
优秀其它推荐
热门其它
邮箱： 