emm不是acwing练习赛,是牛客练习赛。由于题解里面还没牛客这个选项,就先写acwing了。
题目描述
给定 $n, m(1 \leq n, m \leq 10 ^ 8)$,求
$$ \sum _ {i _ 1 = 1} ^ n \sum _ {i _ 2 = 1} ^ n \sum _ {i _ 3 = 1} ^ n \cdots \sum _ {i _ m = 1} ^ n \gcd(f(i _ 1), f(i _ 2), f(i _ 3), \cdots, f(i _ m)) $$
其中 $f(i)$ 表示斐波那契数列第 $i$ 项。
答案模 $10 ^ 9 + 9$。
输入格式
一行两个整数表示 $n, m$。
输出格式
一行一个整数表示答案。
输入样例1
2 2
输出样例1
4
输入样例2
14 5
输出样例2
540956
算法1
(矩阵快速幂,数论分块,莫比乌斯反演,杜教筛) $O(n ^ \frac 2 3 \log m)$
首先斐波那契数列的一个性质 $\gcd(f _ i, f _ j) = f _ {\gcd(i, j)}$。(证明先鸽着) UPD:证明放到了最后。
这个式子也可以推广到多个斐波那契数的最大公约数中,即
$$ \gcd(f _ {i _ 1}, f _ {i _ 2}, \cdots, f _ {i _ m}) = f _ {\gcd(i _ 1, i _ 2, \cdots, i _ m)} $$
将其代入得到
$$ \sum _ {i _ 1 = 1} ^ n \sum _ {i _ 2 = 1} ^ n \cdots \sum _ {i _ m = 1} ^ n f _ {\gcd(i _ 1, i _ 2, \cdots, i _ m)} $$
注意到 $\gcd$ 的范围是 $[1, n]$,那么枚举 $\gcd$,得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {i _ 1 = 1} ^ n \sum _ {i _ 2 = 1} ^ n \cdots \sum _ {i _ m = 1} ^ n [\gcd(i _ 1, i _ 2, \cdots, i _ m) = k] $$
注意到 $\gcd(i _ 1, i _ 2, \cdots, i _ m) = k$ 等价于 $ \left\{ \begin {aligned} & k | i _ 1, k | i _ 2, \cdots, k | i _ m \\\ & \gcd(i _ 1 / k, i _ 2 / k, \cdots, i _ m / k) = 1 \\ \end {aligned} \right. $ (这里默认除法下取整,将下取整负号省去了)
那么上式可化为
$$ \sum _ {k = 1} ^ n f _ k \sum _ {i _ 1 = 1} ^ {n / k} \sum _ {i _ 2 = 1} ^ {n / k} \cdots \sum _ {i _ m = 1} ^ {n / k} [\gcd(i _ 1, i _ 2, \cdots, i _ m) = 1] $$
给后面的东西来个莫比乌斯反演,得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {i _ 1 = 1} ^ {n / k} \sum _ {i _ 2 = 1} ^ {n / k} \cdots \sum _ {i _ m = 1} ^ {n / k} \ \sum _ {d | \gcd(i _ 1, i _ 2, \cdots, i _ m)} \mu(d) $$
交换求和顺序,把 $\begin {aligned} \sum _ d \end {aligned}$ 放到前面来,得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {d = 1} ^ n \mu(d) \sum _ {i _ 1 = 1} ^ {n / k} \sum _ {i _ 2 = 1} ^ {n / k} \cdots \sum _ {i _ m = 1} ^ {n / k} \ [i _ 1 | d] [i _ 2 | d] \cdots [i _ m | d] $$
还是用上面那个性质,把 $i _ j | d$ 放到 $\sum$ 里面,得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {d = 1} ^ n \mu(d) \sum _ {i _ 1 = 1} ^ {n / (k d)} \sum _ {i _ 2 = 1} ^ {n / (k d)} \cdots \sum _ {i _ m = 1} ^ {n / (k d)} 1 $$
注意到 $\begin {aligned} \sum _ {i _ 1 = 1} ^ {n / (k d)} \sum _ {i _ 2 = 1} ^ {n / (k d)} \cdots \sum _ {i _ m = 1} ^ {n / (k d)} 1 = [\frac n {k d}] ^ m \end {aligned}$(可以感性理解为一个长度为 $m$ 的数列,其中每个数都取 $[1, n / (k d)]$ 的整数的方案数)
代入得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {d = 1} ^ n \mu(d) \big[ \frac n {k d} \big] ^ m $$
注意到上面的 $\begin {aligned} \big[ \frac n {k d} \big] ^ m \end {aligned}$ 当 $n < k d$ 时为 $0$,因此 $d$ 可以只枚举到 $n / k$,得到
$$ \sum _ {k = 1} ^ n f _ k \sum _ {d = 1} ^ {n / k} \mu(d) \big[ \frac n {k d} \big] ^ m $$
设 $ \begin {aligned} R(x) = \sum _ {d = 1} ^ x \mu(d) \big[ \frac x d \big] ^ m \end {aligned} $
那么上式即为
$$ \sum _ {k = 1} ^ n f _ k R(n / k) $$
注意到其中 $n / k$ 不超过 $2 \sqrt n$ 种取值,因此可以数论分块。
那么接下来出现了两个问题:
- 快速求 $f _ n$ 的前缀和
- 快速求 $R(x)$
对于第一个问题,这里直接给出结论:
$$ \sum _ {i = 1} ^ n f _ i = f _ {n + 2} - 1 $$
证明可以参考这里{:target=”_blank”}。
因此我们可以通过矩阵快速幂在 $O(\log n)$ 的时间复杂度内求出 $f _ n$ 的前缀和。
对于第二个问题,继续推式子。
$$ R(x) = \sum _ {d = 1} ^ x \mu(d) \big[ \frac x d \big] ^ m $$
注意到 $\begin {aligned} \big[ \frac x d \big] ^ m \end {aligned}$ 可以数论分块,而求 $\mu(d)$ 的前缀和可以用 $\text{Min_25}$ 筛或者杜教筛,这里我使用的是杜教筛。
因此可以在“能过”的时间复杂度内求出 $R(x)$。
对于求 $R(x)$ 的复杂度和整体算法的时间复杂度分析我放到后面。
时间复杂度
杜教筛的复杂度为 $O(n ^ \frac 2 3) \sim O(n ^ \frac 3 4)$,我这里预处理到了 $2 \times 10 ^ 6$,所以这里复杂度应该是 $O(n ^ \frac 3 4)$。
求 $R(x)$ 的复杂度:
在 $R(x)$ 的计算中,我们要求 $\sqrt x$ 次 $\mu(x)$ 的前缀和,这部分复杂度总就是上面杜教筛复杂度,即 $O(n ^ \frac 3 4)$。
另外,我们需要求 $O(\sqrt x)$ 次 $\begin {aligned} \big[ \frac x d \big] ^ m \end {aligned}$,这部分复杂度共为 $O(\sqrt x \log m)$。
在计算答案(即 $\begin {aligned} \sum _ {k = 1} ^ n f _ k R(n / k) \end {aligned}$)时,我们要调用 $\sqrt n$ 次快速幂,这部分复杂度是 $O(\sqrt n \log n)$。
另外,我们会求 $\sqrt n$ 次 $R(x)$,但这里每次的 $x$ 是不同的,因此我们要分别分析。
设计算 $R(x)$ 的复杂度是 $T(x)$,那么算法的总复杂度为 $O(n ^ \frac 3 4 + \sqrt n \log n + \begin {aligned} \sum _ {x \in \{n / k\}} \end {aligned} T(x))$,其中 $\{n / k\}$ 表示 $n / k$ 的所有取值。
我们可以将 $\begin {aligned} \sum _ {x \in \{n / k\}} \end {aligned} T(x)$ 拆成 $1 \leq k \leq \sqrt n$ 和 $\sqrt n < k \leq n$ 这两部分计算。
当 $1 \leq k \leq \sqrt n$ 时,$n / k$ 的取值不重复,因此这部分复杂度为 $\begin {aligned} \sum _ {k = 1} ^ {\sqrt n} T(n / k) \end {aligned}$。
当 $\sqrt n < k \leq n$ 时,$n / k$ 的取值取遍 $[1, \sqrt n]$,因此这部分复杂度为 $\begin {aligned} \sum _ {k = 1} ^ \sqrt n T(k) \end {aligned}$。
因此 $\begin {aligned} \sum _ {x \in \{n / k\}} T(x) = \sum _ {k = 1} ^ {\sqrt n} T(k) + \sum _ {k = 1} ^ {\sqrt n} T(n / k) \end {aligned}$。
根据上面对 $R(x)$ 的复杂度的推导,有 $T(x) = O(\sqrt x \log m)$
那么
$$ \sum _ {k = 1} ^ {\sqrt n} T(k) = O(\sum _ {k = 1} ^ {\sqrt n} \sqrt k \log m) \sim O(\log m \int _ 1 ^ {\sqrt n} \sqrt x \text d x) $$
而
$$ \int _ 1 ^ {\sqrt n} \sqrt x \text d x = \frac 2 3 x ^ \frac 3 2 \bigg | _ 1 ^ \sqrt n = \frac 2 3 n ^ \frac 3 4 - \frac 2 3 $$
所以 $\begin {aligned} \sum _ {k = 1} ^ \sqrt n T(k) = O(n ^ \frac 3 4 \log m) \end {aligned}$
同样,
$$ \sum _ {k = 1} ^ {\sqrt n} T(n / k) = O(\sum _ {k = 1} ^ {\sqrt n} \sqrt \frac n k \log m) \sim O(\log m \int _ 1 ^ {\sqrt n} \sqrt \frac n x \text d x) $$
而
$$ \int _ 1 ^ {\sqrt n} \sqrt \frac n x \text d x = 2 \sqrt n x ^ \frac 1 2 \bigg | _ 1 ^ \sqrt n = 2 n ^ \frac 3 4 - 2 \sqrt n $$
所以 $\begin {aligned} \sum _ {k = 1} ^ \sqrt n T(n / k) = O(n ^ \frac 3 4 \log m) \end {aligned}$
所以 $\begin {aligned} \sum _ {x \in \{n / k\}} T(x) = O(n ^ \frac 3 4 \log m) \end {aligned}$
那么总复杂度即为 $O(n ^ \frac 3 4 \log m)$。当 $n = m = 10 ^ 8$ 的时候大概是 $2.7 \times 10 ^ 7$ 左右。
C++ 代码
#include <cstdio>
#include <cstring>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int N = 2000005;
const int mod = 1e9 + 9;
inline int power(int x, int k) {
int r = 1;
while (k) {
if (k & 1) r = (ll)r * x % mod;
x = (ll)x * x % mod;
k >>= 1;
}
return r;
}
struct Matrix {
int w[2][2];
inline void set(const int c) { // 初始化成 O 或初始化成 E
w[0][0] = w[1][1] = c;
w[0][1] = w[1][0] = 0;
}
};
// 重载矩阵乘法
inline Matrix operator * (const Matrix& a, const Matrix& b) {
static Matrix res;
res.w[0][0] = ((ll)a.w[0][0] * b.w[0][0] + (ll)a.w[0][1] * b.w[1][0]) % mod;
res.w[0][1] = ((ll)a.w[0][0] * b.w[0][1] + (ll)a.w[0][1] * b.w[1][1]) % mod;
res.w[1][0] = ((ll)a.w[1][0] * b.w[0][0] + (ll)a.w[1][1] * b.w[1][0]) % mod;
res.w[1][1] = ((ll)a.w[1][0] * b.w[0][1] + (ll)a.w[1][1] * b.w[1][1]) % mod;
return res;
}
// 矩阵快速幂
inline Matrix power(const Matrix& _x, int k) {
static Matrix r, x;
x = _x, r.set(1);
while (k) {
if (k & 1) r = r * x;
x = x * x;
k >>= 1;
}
return r;
}
// 求斐波那契数列第 x 项
inline int f(int x) {
static Matrix A;
A.w[0][0] = 0, A.w[0][1] = A.w[1][0] = A.w[1][1] = 1;
return power(A, x - 1).w[1][1];
}
// 杜教筛求 mu(x)
unordered_map<int, int> S;
int bs[N], primes[N], cnt;
bool st[N];
void prework() {
bs[1] = 1;
for (int i = 2; i < N; ++i) {
if (!st[i]) primes[cnt++] = i, bs[i] = -1;
for (int j = 0; i * primes[j] < N; ++j) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
bs[i * primes[j]] = -bs[i];
}
bs[i] += bs[i - 1];
}
}
inline int s(int x) { // 这里将 mu(x) 的前缀和记为 s(x)
if (x < N) return bs[x];
if (S.count(x)) return S[x];
int res = 1;
for (int l = 2, r; l <= x; l = r + 1) {
r = x / (x / l);
res -= s(x / r) * (r - l + 1);
}
return S[x] = res;
}
int n, m, res;
// 求上文所述的 R(x)
inline int R(int x) {
int res = 0;
for (int l = 1, r; l <= x; l = r + 1) {
r = x / (x / l);
res = (res + (ll)power(x / r, m) * (s(r) - s(l - 1))) % mod;
}
return res;
}
int main() {
prework();
scanf("%d%d", &n, &m);
for (int l = 1, r; l <= n; l = r + 1) {
r = n / (n / l);
res = (res + (ll)(f(r + 2) - f(l + 1) + mod) * R(n / r)) % mod;
}
printf("%d\n", res);
return 0;
}
命题:若数列 $f$ 满足 $\left\{ \begin {aligned} & f _ 0 = 0, f _ 1 = 1 \\\ & f _ {n + 2} = f _ n + f _ {n + 1} (n \geq 0) \end {aligned} \right.$,则对于任意的 $i, j \geq 1$,有 $\gcd(f _ i, f _ j) = f _ {\gcd(i, j)}$。
证明:命题中 $i, j$ 是对称的,不妨设 $i \leq j$,那么只需证明 $\gcd(f _ i, f _ j) = \gcd(f _ i, f _ {j - i})$,再根据辗转相除法,就证明了上述命题。
引理1:$f _ j = f _ {k + 1} f _ {j - k} + f _ k f _ {j - k - 1} (0 \leq k < j)$
证明:当 $k = 0$ 时,$f _ {k + 1} f _ {j - k} + f _ k f _ {j - k - 1} = f _ 1 f _ j + f _ 0 f _ {j - 1} = f _ j$,引理 1 成立。
假设当 $k = i - 1 (0 < i < j)$ 时成立,那么有 $f _ j = f _ i f _ {j - i + 1} + f _ {i - 1} f _ {j - i}$,考虑当 $k = i$ 时:
$$ \begin {aligned} & f _ {i + 1} f _ {j - i} + f _ i f _ {j - i - 1} \\\ = & (f _ i + f _ {i - 1}) f _ {j - i} + f _ i f _ {j - i - 1} \\\ = & f _ {i - 1} f _ {j - i} + f _ i f _ {j - i} + f _ i f _ {j - i - 1} \\\ = & f _ {i - 1} f _ {j - i} + f _ i (f _ {j - i} + f _ {j - i - 1}) \\\ = & f _ {i - 1} f _ {j - i} + f _ i f _ {j - i + 1} \\\ = & f _ j \\\ \end {aligned} $$
所以若 $k = i - 1$ 时引理成立,则 $k = i$ 时引理 1 成立。证毕。
引理2:$\gcd(f _ i, f _ {i + 1}) = 1 (i \geq 0)$
证明:
$$ \begin {aligned} & \gcd(f _ i, f _ {i + 1}) \\\ = & \gcd(f _ i, f _ i + f _ {i - 1}) \\\ = & \gcd(f _ i, f _ {i - 1}) \\\ = & \gcd(f _ {i - 1}, f _ {i - 2}) \\\ \quad & \cdots \\\ = & \gcd(f _ 1, f _ 0) \\\ = & 1 \end {aligned} $$
证毕。
根据引理1,有$f _ j = f _ {i + 1} f _ {j - i} + f _ i f _ {j - i - 1}$,那么
$$ \begin {aligned} & \gcd(f _ i, f _ j) \\\ = & \gcd(f _ i, f _ {i + 1} f _ {j - i} + f _ i f _ {j - i - 1}) \\\ = & \gcd(f _ i, f _ {i + 1} f _ {j - i}) \end {aligned} $$
根据引理2,因为 $\gcd(f _ i, f _ {i + 1}) = 1$,所以 $\gcd(f _ i, f _ {i + 1} f _ {j - i}) = \gcd(f _ i, f _ {j - i})$。
所以 $\gcd(f _ i, f _ j) = \gcd(f _ i, f _ {j - i})$。证毕。
$$ $$
求求讲一讲C题
emm那题我暴力容斥的,我感觉我说不清楚思路。。。
气死我了我写的线性做法,一直被卡空间,垃圾牛客
(线性做法空间不是$\text{400MB}$?
我最后要开一个bool和一个short的1e8
bool
改成bitset
没准就过了(bushi