洛谷P3263题解报告

发表于 更新于 分类于

洛谷P3263

题意描述

给定 $b$、$d$ 和 $n$。

试求出：

$\left \lfloor \left ( \frac{b+\sqrt{d} }{2} \right )^{n} \right \rfloor \bmod{p} $

其中 $p=7528443412579576937$ ，$0 < b^{2} \le d < (b+1)^{2}\le 10^{18}$，$n\le 10^{18}$ 且 $b\bmod{2}=1$，$d \bmod{4}=1$。

题解报告

式子较为复杂，看了下标签是“矩阵乘法”，更加蒙了。（原本都打算搞个 $double$ 的矩阵了。。。）

想要让式子与矩乘挂上钩，首先想到要把那个根号给去掉。于是想到在原式后加一个式子使两者相加能将根号去掉。

由于有一个 $n$，可以想到将带根号的那一项取负，其他不变（暂不考虑取模和向下取整），然后原式变为：

$\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$

在原式后加上现在这个式子便可将根号消掉，即：

$\left ( \frac{b+\sqrt{d} }{2} \right )^{n}+ \left ( \frac{b-\sqrt{d} }{2} \right )^{n}$

然后在式子最后减去一个 $\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 就好了。

设 $x$ 为 $\frac{b+\sqrt{d} }{2}$，$y$ 为 $\frac{b-\sqrt{d} }{2}$。

设 $f_{n}=x^{n}+y^{n}$。

那么可以设我们的状态矩阵为：

$\begin{bmatrix} f_{n}&f_{n-1} \end{bmatrix}$

需要通过

$\begin{bmatrix} f_{n-1}&f_{n-2} \end{bmatrix}$

转移到

$\begin{bmatrix} f_{n}&f_{n-1} \end{bmatrix}$

接下来考虑如何转移。

将 $f_{n}$ 拆成 $X\times f_{n-1}-X\times f_{n-2}$ 的形式，又因为 $f_{n-1}=x^{n-1}+y^{n-1}$，$f_{n-2}=x^{n-2}+y^{n-2}$，代入得：

$X\times \left ( x^{n-1}+y^{n-1} \right ) -X\times \left ( x^{n-2}+y^{n-2} \right )$

于是稍加考虑就可以得出：

$x^{n}+y^{n}=\left ( x+y \right ) \times \left ( x^{n-1}+y^{n-1} \right ) - xy \times \left ( x^{n-2}+y^{n-2} \right )$

所以转移式为：

$f_{n}=\left ( x+y \right ) \times f_{n-1}- xy \times f_{n-2}$

能保证这个式子中没有任何浮点数吗？

我们发现 $f_{1}=\frac{b+\sqrt{d} }{2}+\frac{b-\sqrt{d} }{2}=b$，$f_{2}= \left ( \frac{b+\sqrt{d} }{2} \right )^{2}+ \left ( \frac{b-\sqrt{d} }{2} \right )^{2} = \frac{b^{2}+d }{2}$。

$b$ 一定是整数，而由于 $b\bmod{2}=1$，$d \bmod{4}=1$，由费马小定理可得 $b^{2}\equiv b \pmod{2}$，所以 $b^{2}+d \bmod{2}=0$，所以 $\frac{b^{2}+d }{2}$ 也是整数。

于是乎，$f_{1}$ 和 $f_{2}$ 都是整数，接下来只需证明出他俩前面的系数也是整数就好了。

首先易得 $x+y=b$，所以 $x+y$ 是整数，然后 $xy=\frac{b^{2}-d}{4}$，由欧拉定理可得 $b^{\varphi (4)}=b^{2}\equiv 1\pmod{4}$，又因为 $d \bmod{4}=1$，所以 $\left ( b^{2}-d \right ) \bmod 4=0$，所以 $xy$ 为整数。

综上，$f_{n}$ 总为整数。

所以转移矩阵也同时推出来了。

如下：

$\begin{bmatrix} b &1 \\ -\frac{b^{2}-d}{4} &0\end{bmatrix}$

这里的 $-\frac{b^{2}-d}{4}$ 为了方便可以写成 $\frac{d-b^{2}}{4}$。

最后再来看看刚才这个东西对答案的影响：

然后在式子最后减去一个 $\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 就好了。

由于答案是向下取整，所以当 $-\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 为正且大小在区间 $\left [ 0,1 \right )$ 时对答案无影响。

由于 $0 < b^{2} \le d < (b+1)^{2}\le 10^{18} $，所以 $\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 的范围一定在区间 $\left [ 0,1 \right )$ 内。

接下来只要讨论式子的正负性。

因为 $0 < b^{2} \le d$，所以 $\frac{b-\sqrt{d} }{2}$ 一定小于 0。

当 $n \bmod{2}=1$ 时，即 $n$ 为奇数时，$-\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 一定的范围一定在 $\left [ 0,1 \right )$ 内，对答案没有影响。

相反，当 $n \bmod{2}=0$ 时，$-\left ( \frac{b-\sqrt{d} }{2} \right )^{n}$ 的范围在区间 $\left ( -1,0 \right ]$ 内。当式子等于 0 时,即 $b=\sqrt{d}$，$b^{2}=d$ 时，该式对答案无影响。

综上，当且仅当 $n$ 为偶数且 $b^{2} \ne d$ 时，该式对答案有影响，答案向下取整后的值需要减一。

说了一大堆，终于到了大家最爱的代码时间。

嗲吗

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
#define int long long
#define ull unsigned long long

int tormul(int a, int k) 
{  //龟速乘
	ull ans = 0;  //注意要开 ull，否则会 TLE！！（玄学 T，难道不应该 WA 吗）
	while (k) 
	{
		if (k & 1)ans = (ans + a) % MOD;
		a = (ull)(a + a) % MOD;  //开 ull。
		k >>= 1;
	}
	return ans;
}
struct mat 
{
	int a[2][2];
	mat() { memset(a, 0, sizeof a); }
	mat operator *(const mat &b)const 
	{
		mat op;
		for (int i = 0; i < 2; i++) 
			for (int k = 0; k < 2; k++) 
				for (int j = 0; j < 2; j++) 
					op.a[i][j] = (ull)(op.a[i][j] + tormul(a[i][k], b.a[k][j])) % MOD;  //ull
		return op;
	}
} ans, I;
void init() 
{
	I.a[0][0] = b, I.a[0][1] = 1, I.a[1][0] = (d - b * b) / 4;
	ans.a[0][0] = (b * b + d) / 2, ans.a[0][1] = b;
}
signed main() 
{
	b = read(), d = read(), n = read();
	init();
	if (n == 0ll) 
	{
		printf("1");
		return 0;
	} else if (n == 1ll) 
	{
		printf("%lld ", (int)((b + sqrt(d)) / 2) % MOD);
		return 0;
	}
	n -= 2;
	int ff = 0; //用来判断最后减去的式子对答案是否有影响。
	if (b * b != d && n % 2 == 0) ff--;
	while (n) 
	{
		if (n & 1)ans = ans * I;
		I = I * I;
		n >>= 1;
	}
	ans.a[0][0] += ff;
	printf("%lld ", ans.a[0][0]);
	return 0;
}

有错误请 D 我