「BZOJ 2813」奇妙的 Fibonacci-线性筛

Fibonacci 数列是这样一个数列:
$F_1 = 1, F_2 = 2, F_3 = 3 \cdots$ $F_i = F_{i - 1} + F_{i - 2}$ (当 $i \geq 3$)
pty 忽然对这个古老的数列产生了浓厚的兴趣,他想知道:对于某一个 Fibonacci 数 $F_i$,有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$),他还想知道所有 $j$ 的平方之和是多少。

链接

BZOJ 2813

题解

首先 $\gcd(f_n, f_{n + 1}) = 1$,证明如下:
$$\begin{aligned}\gcd(f_n, f_{n + 1}) &= \gcd(f_{n + 1} - f_n, f_n) \\ &= \gcd(f_{n - 1}, f_n) \\ &\cdots \\ &= \gcd(f_1, f_2) \\ &= 1 \end{aligned}$$

然后有一个结论 $f_{m + n} = f_{m - 1} * f_n + f_m * f_{n + 1}$,证明如下:
$$\begin{aligned}f_{m + n} &= f_{m + n - 1} + f_{m + n - 2} \\ &= 2 * f_{n + m - 2} + f_{n + m - 3} \\ &= a_x * f_{n + m - x} + b_x * f_{n + m - x - 1} \\ &= (a_x + b_x) * f_{n + m - x - 1} + a_x * f_{n + m - x - 2} \end{aligned}$$
当 $x = 1$ 时,$a_x = 1 = f_2,\ b_x = 1 = f_1$,由于 $a_{x + 1} = a_x + b_x,\ b_{x + 1} = a_x$,所以 $x = n$ 时,$a_x = f_{n + 1},\ b_x = f_n$。
令 $x = m - 1$,则 $f_{m + n} = f_{m - 1} \cdot f_n + f_m \cdot f_{n + 1}$。

以及 $\gcd(f_{m + n}, f_n) = \gcd(f_m, f_n)$,证明如下:
$$\begin{aligned}\gcd(f_{m + n}, f_n) &= \gcd(f_m * f_{n + 1} + f_n * f_{m - 1}, f_n) \\ &= \gcd(f_m * f_{n + 1}, f_n) \\ &= \gcd(f_m, f_n) * \gcd(f_{n + 1}, f_n) \\ &= \gcd(f_n, f_m) \end{aligned}$$

根据更相减损术,设 $m = p_1 * n + r_1,\ n = p_2 * r_1 + r_2,\ r_1 = p_3 * r_2 + r_3,\cdots$,则
$$\gcd(m, n) = \gcd(n, r_1) = \cdots = r_x$$

$$\gcd(f_m, f_n) = \gcd(f_n, f_{r_1}) = \cdots = f_{r_x} = f_{\gcd(m, n)}$$

故 $f_j\ | \ f_i \Leftrightarrow j \ | \ i$。
所以答案就是因数个数以及因数平方和,但由于 $f_2 = 1$,$q_i$ 若是奇数那么因数和要 $+1$,而因数平方和要 $+4$,我们可以用快速线性筛选法预处理,令 $idx[i]$ 为 $i$ 的最小质因数的指数,$d[i]$ 为 $i$ 除去最小质因子的数,$cnt[i]$ 为 $i$ 的因数个数,$sum[i]$ 为 $i$ 的因数平方和。

设 $x = p_1 ^ {k_1} * p_2 ^ {k_2} * \cdots * p_n ^ {k_n}$,根据乘法原理,$cnt[x] = (k_1 + 1) * (k_2 + 1) * \cdots * (k_n + 1)$,因为每个质因数 $p_i$ 都可以提供 $0 \sim k_i$ 个 $p_i$ 来构造新约数,即 $k_i + 1$ 种可能。

显然 $cnt$ 为积性函数,对于一个数 $i$,当 $i$ 为质数时,
$cnt[i] = 2,\ idx[i] = 1,\ d[i] = 1,\ sum[i] = i ^ 2 + 1$。

接下来先分析 $cnt,\ idx$:

  1. 当 $i$ 的最小质因子 $p$ 的指数为 $1$ 的时,显然 $i\ /\ p$ 与 $p$ 是互质的,由于 $cnt$ 是积性函数,$cnt[i] = cnt[i / p] * cnt[p] = cnt[i / p] * 2$。
  2. 当 $i$ 的最小质因子 $p$ 的指数不为 $1$ 的时,因为最小质因子的次数增加了 $1$,所以只要把 $cnt[i / p]$ 里面质因子 $p$ 贡献的那一部分改一下就可以了,因为一开始 $p$ 的指数为 $idx[i / p]$,为 $cnt[i / p]$ 贡献的那一部分是 $idx[i / p] + 1$,那么乘上一个 $p$ 有$$idx[i] = idx[i / p] + 1$$ 则$$cnt[i] = \frac {cnt[i / p]} {idx[i / p]} * (idx[i] + 1)$$

下面考虑快速线性筛选法中的情况:

  1. 当 $i \text{ mod } prime[j] > 0$ 时,$i * prime[j]$ 第一次遇见最小质因数,因数个数乘 $2$,$sum[i * prime[j]]$ 为 $sum[i] * prime[j] ^ 2 + sum[i]$(每个因子乘或不乘 $prime[j]$)。
  2. 当 $i \text{ mod } prime[j] = 0$ 时,$prime[j]$ 为 $i * prime[j]$ 的最小质因数但已经遇见过,最小质因数加 $1$,因数个数关于最小质因数部分重算,$d[i * prime[j]]$ 不变,$sum[i* prime[j]]$ 为 $sum[i] * prime[j] ^ 2 + sum[d[i * prime[j]]]$。

故时间复杂度为 $O(Q + C)$。

代码

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
/**
* Copyright (c) 2017, xehoth
* All rights reserved.
* 「BZOJ 2813」奇妙的 Fibonacci 09-07-2017
* 线性筛
* @author xehoth
*/
#include <bits/stdc++.h>
namespace FastLinearSieveMethod {
#define long long long
const int MAXC = 664580, MAXN = 10000001, MOD = 1000000007;
int tot, prime[MAXC], idx[MAXN], d[MAXN], cnt[MAXN], sum[MAXN], ans1, ans2;
bool vis[MAXN];
inline void fastLinearSieveMethod(int C) {
cnt[1] = sum[1] = 1;
for (register int i = 2; i <= C; i++) {
if (!vis[i]) {
prime[tot++] = i, idx[i] = d[i] = 1;
cnt[i] = 2, sum[i] = ((long)i * i + 1) % MOD;
}
for (register int j = 0, k; j < tot && (k = i * prime[j]) <= C; j++) {
vis[k] = true;
if (i % prime[j] == 0) {
idx[k] = idx[i] + 1;
cnt[k] = (cnt[i] / (idx[i] + 1)) * (idx[k] + 1), d[k] = d[i];
sum[k] =
(sum[i] * ((long)prime[j] * prime[j] % MOD) + sum[d[i]]) %
MOD;
break;
} else {
idx[k] = 1, d[k] = i, cnt[k] = cnt[i] << 1;
sum[k] = sum[i] * (((long)prime[j] * prime[j] + 1) % MOD) % MOD;
}
}
}
}
inline void solve() {
int Q, q, A, B, C;
scanf("%d%d%d%d%d", &Q, &q, &A, &B, &C);
A %= C, B %= C;
fastLinearSieveMethod(C);
while (Q--) {
ans1 += cnt[q] + (q & 1);
ans2 += sum[q] + 4 * (q & 1);
ans1 >= MOD ? ans1 -= MOD : 0;
ans2 >= MOD ? ans2 -= MOD : 0;
q = (q * (long)A + B) % C + 1;
}
printf("%d\n%d\n", ans1, ans2);
}
}
int main() {
FastLinearSieveMethod::solve();
return 0;
}
分享到