「BZOJ 4833」最小公倍佩尔数

Posted on | Edited on | In , ,

Problem

Description

定义 \left(1 + \sqrt{2}\right)^{n} = e_{n} + f_{n}\sqrt{2} (e_{n}, f_{n} \in \mathbb{Z}), \DeclareMathOperator*{\lcm}{lcm} g_{n} = \lcm_{i = 1}^{n} f_{i} 。
给定 n, p ，求 \sum\limits_{i = 1}^{n} i g_{i} \pmod {p} 。

Constraints

1 \le n \le 10^{6}, 2 \le p \le 10^{9} + 7

保证 p 为质数且 \forall i \in [1, n] : f_{i} \bmod{p} \ne 0 。

Solution

Analysis

首先容易发现 f_{n} 的递推式为 f_{n} = 2f_{n - 1} + f_{n - 2} ，边界条件为 f_{0} = 0, f_{1} = 1 。
则这是一个广义斐波那契数列。
又因 \gcd(2, 1) = 1 （其中 2, 1 为递推系数），则有 \gcd(f_{i}, f_{j}) = f_{\gcd(i, j)} 。

现在已经有了转化 \gcd 的方法，但是题目要求的是 \lcm ，于是考虑转化。
对每个质因子的次数进行 min-max 容斥可得：

\lcm_{i \in S} f_{i} = \prod_{T \subseteq S} [|T| > 0] \left(\gcd_{i \in T} f_{i}\right)^{(-1)^{|T| - 1}} = \prod_{T \subseteq S} [|T| > 0] f_{\gcd{T}}^{(-1)^{|T| - 1}}

构造数列 \{g_{n}\} 使得其满足 f_{n} = \prod\limits_{d | n} g_{d} 亦即 g = f \ast \mu ，那么就有：

\begin{aligned} \lcm_{i = 1}^{n} f_{i} &= \prod_{T \subseteq [n]} [|T| > 0] f_{\gcd{T}}^{(-1)^{|T| - 1}} \\ &= \prod_{T \subseteq [n]} [|T| > 0] \left(\prod_{d \mid \gcd{T}} g_{d}\right)^{(-1)^{|T| - 1}} \\ &= \prod_{i = 1}^{n} g_{i}^{\sum_{T \subseteq [n]} [|T| > 0] [i \mid \gcd{T}] (-1)^{|T| - 1}} \end{aligned}

记 S_{d} := \{x : x \in S, d \mid x\} ，考虑 g_{d} 的指数，有：

\begin{aligned} \sum_{T \subseteq S} [|T| > 0] [d \mid \gcd{T}] (-1)^{|T| - 1} &= \sum_{T \subseteq S_{d}} [|T| > 0] (-1)^{|T| - 1} \\ &= \sum_{i = 1}^{|S_{d}|} \binom{|S_{d}|}{i} (-1)^{i - 1} \\ &= -\sum_{i = 0}^{|S_{d}|} \binom{|S_{d}|}{i} (-1)^{i} + \binom{|S_{d}|}{0} (-1)^{0} \\ &= -(1 - 1)^{|S_{d}|} + 1 \\ &= [|S_{d}| \ne 0] \end{aligned}

故：

\lcm_{i = 1}^{n} f_{i} = \prod_{i = 1}^{n} g_{i}^{[|[n]_{i}| \ne 0]} = \prod_{i = 1}^{n} g_{i}

对于 g_{i} ，根据其定义式移项可得：

g_{n} = f_{n} \left(\prod_{d \mid n} [d \ne n] g_{d} \right)^{-1}

直接按定义式求就可以了。

时间复杂度 O(n \log{n}) 。

Code

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
#include <cstdio>

typedef long long i64;

const int maxn = 1000000;

inline int io() {
	static int v;
	return scanf("%d", &v), v;
}

inline int fpow(int v, int n, const int &mod) {
	int pw = 1;
	for (; n; n >>= 1, v = (i64)v * v % mod)
		if (n bitand 1) pw = (i64)pw * v % mod;
	return pw;
}

int main() {
	static int f[maxn + 1];
	for (int T = io(); T; --T) {
		const int n = io(), mod = io();

		f[1] = 1;
		for (int i = 2; i <= n; ++i)
			f[i] = (f[i - 1] * 2ll + f[i - 2]) % mod;

		for (int i = 1; i <= n; ++i) {
			const int inv = fpow(f[i], mod - 2, mod);
			for (int j = i + i; j <= n; j += i)
				f[j] = (i64)f[j] * inv % mod;
		}
		for (int i = 2; i <= n; ++i)
			f[i] = (i64)f[i] * f[i - 1] % mod;

		i64 ans = 0;
		for (int i = 1; i <= n; ++i)
			ans += (i64)i * f[i] % mod;
		printf("%lld\n", ans % mod);
	}

	return 0;
}