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

Fibonacci 数列是这样一个数列：

pty 忽然对这个古老的数列产生了浓厚的兴趣，他想知道：对于某一个 Fibonacci 数 $F_i$，有多少个 $F_j$ 能够整除 $F_i$ ($i$ 可以等于 $j$)，他还想知道所有 $j$ 的平方之和是多少。

链接

BZOJ 2813

题解

首先 $\gcd(f_n, f_{n + 1}) = 1$，证明如下：

然后有一个结论 $f_{m + n} = f_{m - 1} * f_n + f_m * f_{n + 1}$，证明如下：

当 $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)$，证明如下：

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

故

故 $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,\ 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;
}