[转] 广义Fibonacci数列找循环节

出处

转自ACDreamer的博客

问题

给定img-1,满足img-2,求img-3的循环节长度。

分析

我们知道矩阵的递推关系如下:

img-4

然后继续有:

img-5

那么,现在的问题就转化为求最小的img-6,使得img-7

所以我们可以先找出符合条件的一个img-8,然后枚举它的因子,找最小的。设

img-9

为了好解决问题,我们需要对矩阵img-10进行相似对角化,即img-11的特征值

解得img-11的特征值为img-12

也就是说img-12的相似对角矩阵img-13

img-14

因为我们知道img-15,所以当img-16时,img-17,由于

img-18

继续得到

img-19

img-20,那么分情况讨论:

  1. img-21是模img-22的二次剩余,由费马小定理得img-23时,img-24
  2. img-24是模img-22的二次非剩余,则有

    img-25,根据欧拉准则有

    img-26

    那么继续得到

    img-27

    然后由费马小定理有img-28,同理有img-29所以,当img-30时,img-31

  3. img-32时,由于img-33不存在,所以无法完成相似对角化,好在img-34情况不存在。

所以综上所述:

  • img-35是模img-36的二次剩余时,枚举img-37的因子
  • img-35是模img-36的二次非剩余时,枚举img-38的因子

找最小的因子img-39使得

img-40

成立

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 2;
const LL MOD = 1000000007;
LL fac[2][505];
int cnt,ct;
LL pri[6] = {2, 3, 7, 109, 167, 500000003};
LL num[6] = {4, 2, 1, 2, 1, 1};
struct Matrix
{
LL m[N][N];
} ;
Matrix A;
Matrix I = {1, 0, 0, 1};
Matrix multi(Matrix a,Matrix b)
{
Matrix c;
for(int i=0; i<N; i++)
{
for(int j=0; j<N; j++)
{
c.m[i][j] =0;
for(int k=0; k<N; k++)
{
c.m[i][j] += a.m[i][k] * b.m[k][j];
c.m[i][j] %= MOD;
}
}
}
return c;
}
Matrix power(Matrix A,LL n)
{
Matrix ans = I, p = A;
while(n)
{
if(n & 1)
{
ans = multi(ans,p);
n--;
}
n >>= 1;
p = multi(p,p);
}
return ans;
}
LL quick_mod(LL a,LL b)
{
LL ans = 1;
a %= MOD;
while(b)
{
if(b & 1)
{
ans = ans * a % MOD;
b--;
}
b >>= 1;
a = a * a % MOD;
}
return ans;
}
LL Legendre(LL a,LL p)
{
LL t = quick_mod(a,(p-1)>>1);
if(t == 1) return 1;
return -1;
}
void dfs(int dept,LL product = 1)
{
if(dept == cnt)
{
fac[1][ct++] = product;
return;
}
for(int i=0; i<=num[dept]; i++)
{
dfs(dept+1,product);
product *= pri[dept];
}
}
bool OK(Matrix A,LL n)
{
Matrix ans = power(A,n);
return ans.m[0][0] == 1 && ans.m[0][1] == 0 &&
ans.m[1][0] == 0 && ans.m[1][1] == 1;
}
int main()
{
fac[0][0] = 1;
fac[0][1] = 2;
fac[0][2] = 500000003;
fac[0][3] = 1000000006;
LL a,b,c,d;
while(cin>>a>>b>>c>>d)
{
LL t = a * a + 4 * b;
A.m[0][0] = a;
A.m[0][1] = b;
A.m[1][0] = 1;
A.m[1][1] = 0;
if(Legendre(t,MOD) == 1)
{
for(int i=0; i<4; i++)
{
if(OK(A,fac[0][i]))
{
cout<<fac[0][i]<<endl;
break;
}
}
}
else
{
ct = 0;
cnt = 6;
dfs(0,1);
sort(fac[1],fac[1]+ct);
for(int i=0;i<ct;i++)
{
if(OK(A,fac[1][i]))
{
cout<<fac[1][i]<<endl;
break;
}
}
}
}
return 0;
}