hdu5848 Easy Homework

题面传送门

感觉非常恶心的数学题…………
首先我们需要先发现这个等式$f_{n}^{2}-f_{n-1}f_{n+1}=(-1)^{n}$
证明的话把通项公式代入,再联系该数列的特征方程并利用韦达定理就行了
对$n$分奇偶性讨论,
然后令$f_{n} = x,f_{n - 1} = y$的话就是一个关于$y$的一元二次方程了
利用二次剩余解出$y$,没有二次剩余就无解
有了$x,y$就相当于有了终状态$B$
构造转移矩阵$A$求$A^{k}=B\%p$的解,可以用BSGS实现
另一个难点可能是BSGS的范围……
我们知道这个数列在模$p$意义下是有循环节的,对于这道题,循环节规模在$O(p)$量级,可以利用通用的矩阵的循环节公式求得最小循环节……这个循环节大小就是BSGS的范围
有点卡常数……需要手写hash表才行……
或许是我写得太挫了

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
const int maxn = 1e5 + 5;
int mod, wf;
default_random_engine generator(time(NULL));
uniform_int_distribution<LL> df(1, 1e18);
int add(int x, int y) {
x += y;
if(x >= mod) x -= mod;
return x;
}
int mul(int x, int y) {
LL z = 1LL * x * y;
return z - z / mod * mod;
}
int powt(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = mul(r, a);
a = mul(a, a);
b >>= 1;
}
return r;
}
template<typename T, typename U>
struct HashMap {
static const int M = 333331;
int chk[M], cn;
int q[M], qn;
vector<T> a;
vector<U> b;
int fst[M], m;
vector<int> nxt;
HashMap() {
memset(fst, -1, sizeof fst);
cn++;
}
void clear() {
for (int i = 0; i < qn; i++) fst[q[i]] = -1;
cn++;
qn = m = 0;
a.clear(), b.clear(), nxt.clear();
}
U& operator[](T x) {
int r = (x % M + M) % M;
for (int e = fst[r]; ~e; e = nxt[e]) {
if (a[e] == x) {
return b[e];
}
}
if (chk[r] != cn) {
chk[r] = cn;
q[qn++] = r;
}
a.push_back(x), b.push_back(U());
nxt.push_back(fst[r]), fst[r] = m++;
return b.back();
}
bool count(T x) {
int r = (x % M + M) % M;
for (int e = fst[r]; ~e; e = nxt[e]) {
if (a[e] == x) {
return 1;
}
}
return 0;
}
};
const int msize = 2;
struct matrix {
int a[msize][msize];
void clear() {
memset(a, 0, sizeof(a));
}
matrix operator *(const matrix &b) const {
matrix tmp;
tmp.clear();
for(int i = 0; i < msize; i++) {
for(int j = 0; j < msize; j++) {
for(int k = 0; k < msize; k++) {
tmp.a[i][j] = add(tmp.a[i][j], mul(a[i][k], b.a[k][j]));
}
}
}
return tmp;
}
bool operator ==(const matrix &b) const {
for(int i = 0; i < msize; i++) {
for(int j = 0; j < msize; j++) {
if(a[i][j] != b.a[i][j]) return false;
}
}
return true;
}
};
matrix powt(matrix a, LL b) {
matrix r = {1, 0, 0, 1};
while(b) {
if(b & 1) r = r * a;
a = a * a;
b >>= 1;
}
return r;
}
struct node {
int p, d;
node operator * (const node &b) const {
node r;
r.p = add(mul(p, b.p), mul(mul(d, b.d), wf));
r.d = add(mul(p, b.d), mul(d, b.p));
return r;
}
};
node powt(node a, int b) {
node r = node{1, 0};
while(b) {
if(b & 1) r = r * a;
a = a * a;
b >>= 1;
}
return r;
}
int Legendre(int a) {
return powt(a, (mod - 1) >> 1);
}
int get_ans(int x) {
if(x == 0) return 0;
if(powt(x, (mod - 1) >> 1) + 1 == mod) return -1;
int a;
while(true) {
a = df(generator) % mod;
wf = add(mul(a, a), mod - x);
if(Legendre(wf) + 1 == mod) break;
}
node tmp = node{a, 1};
return powt(tmp, (mod + 1) >> 1).p;
}
int pri[maxn], cnt = 0;
void GetPrime() {
for (int i = 2; i < maxn; ++i) {
if (!pri[i]) pri[cnt++] = i;
for (int j = 0; j < cnt && pri[j] * i < maxn; ++j) {
pri[pri[j] * i] = 1;
if (i % pri[j] == 0) break;
}
}
}
vector<int> fac;
void get_fac(int x) {
for(int i = 0; pri[i] * pri[i] <= x; i++) {
while(x % pri[i] == 0) {
fac.push_back(pri[i]);
x /= pri[i];
}
}
if(x > 1) fac.push_back(x);
}
LL get_cycle(int a) {
matrix r = {a, 1, 1, 0};
matrix u = {1, 0, 0, 1};
fac.clear();
get_fac(mod - 1);
//get_fac(mod - 1);
get_fac(mod + 1);
fac.push_back(mod);
int n = fac.size();
LL d = 1;
for(int i = 0; i < n; i++) {
matrix v = r;
for(int j = i + 1; j < n; j++) v = powt(v, fac[j]);
if(u == v) continue;
d *= fac[i];
r = powt(r, fac[i]);
}
return d;
}
HashMap <LL, int> q;
LL solve(int fa, int a, int b, LL len, LL l, LL r, int k) {
int i, j, m = ceil(sqrt(1.0 * len));
LL x, dl, dr, ans = 0;
matrix v = {fa, 1, 1, 0};
matrix u = {add(mul(fa, b), a), b, b, a};
q.clear();
for(i = 0; i < m; i++) {
q[1LL * u.a[0][0] * mod + u.a[1][0]] = i;
u = u * v;
}
u = v = powt(v, m);
for(i = 1; i <= m; i++) {
if(q.count(1LL * u.a[0][0] * mod + u.a[1][0])) {
j = q[1LL * u.a[0][0] * mod + u.a[1][0]];
x = 1LL * i * m - j;
if(x <= len) {
dl = (l - 1) / len;
dr = r / len;
if((l - 1) % len >= x) dl++;
if(r % len >= x) dr++;
if(len & 1) {
if(((x + dl * len) & 1) == k) ans += (dr - dl + 1) / 2;
else ans += (dr - dl) / 2;
} else {
if((x & 1) == k) ans += dr - dl;
}
}
break;
}
u = u * v;
}
return ans;
}
void solve() {
int a, x, u, d, y1, y2, inv;
LL l, r, ans = 0;
scanf("%d%d%d%lld%lld", &a, &mod, &x, &l, &r);
LL len = get_cycle(a);
inv = (mod + 1) >> 1;
d = mul(a, x);
d = add(mul(d, d), mul(4, mul(x, x)));
u = get_ans(add(d, mul(4, mod - 1)));
if(u > 0) {
y1 = mul(add(u, mod - mul(a, x)), inv);
y2 = mul(mod - add(u, mul(a, x)), inv);
ans += solve(a, y1, x, len, l, r, 1);
ans += solve(a, y2, x, len, l, r, 1);
}
u = get_ans(add(d, 4));
if(u > 0) {
y1 = mul(add(u, mod - mul(a, x)), inv);
y2 = mul(mod - add(u, mul(a, x)), inv);
ans += solve(a, y1, x, len, l, r, 0);
ans += solve(a, y2, x, len, l, r, 0);
}
printf("%lld\n", ans);
}
int main() {
#ifdef CX_TEST
freopen("E:\\program--GG\\test_in.txt", "r", stdin);
#endif
int t;
GetPrime();
scanf("%d", &t);
while(t--) solve();
return 0;
}