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

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

链接

BZOJ 2813

题解

首先 gcd(fn,fn+1)=1\gcd(f_n, f_{n + 1}) = 1,证明如下:

gcd(fn,fn+1)=gcd(fn+1fn,fn)=gcd(fn1,fn)=gcd(f1,f2)=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}

然后有一个结论 fm+n=fm1fn+fmfn+1f_{m + n} = f_{m - 1} * f_n + f_m * f_{n + 1},证明如下:

fm+n=fm+n1+fm+n2=2fn+m2+fn+m3=axfn+mx+bxfn+mx1=(ax+bx)fn+mx1+axfn+mx2\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=1x = 1 时,ax=1=f2, bx=1=f1a_x = 1 = f_2,\ b_x = 1 = f_1,由于 ax+1=ax+bx, bx+1=axa_{x + 1} = a_x + b_x,\ b_{x + 1} = a_x,所以 x=nx = n 时,ax=fn+1, bx=fna_x = f_{n + 1},\ b_x = f_n
x=m1x = m - 1,则 fm+n=fm1fn+fmfn+1f_{m + n} = f_{m - 1} \cdot f_n + f_m \cdot f_{n + 1}

以及 gcd(fm+n,fn)=gcd(fm,fn)\gcd(f_{m + n}, f_n) = \gcd(f_m, f_n),证明如下:

gcd(fm+n,fn)=gcd(fmfn+1+fnfm1,fn)=gcd(fmfn+1,fn)=gcd(fm,fn)gcd(fn+1,fn)=gcd(fn,fm)\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=p1n+r1, n=p2r1+r2, r1=p3r2+r3,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,r1)==rx\gcd(m, n) = \gcd(n, r_1) = \cdots = r_x

gcd(fm,fn)=gcd(fn,fr1)==frx=fgcd(m,n)\gcd(f_m, f_n) = \gcd(f_n, f_{r_1}) = \cdots = f_{r_x} = f_{\gcd(m, n)}

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

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

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

接下来先分析 cnt, idxcnt,\ idx

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

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

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

故时间复杂度为 O(Q+C)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;
}
文章目录
  1. 1. 链接
  2. 2. 题解
  3. 3. 代码