洛谷P3263题解报告

发表于 更新于 分类于

洛谷P3263有意义的字符串题解。

洛谷P3263

题意描述

给定 bb、dd 和 nn。

试求出：

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

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

题解报告

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

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

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

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

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

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

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

设 xx 为 b+d2\frac{b+\sqrt{d} }{2}，yy 为 b−d2\frac{b-\sqrt{d} }{2}。

设 f_n=xn+ynf\_{n}=x^{n}+y^{n}。

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

[f_nf_n−1]\begin{bmatrix} f\_{n}&f\_{n-1} \end{bmatrix}

需要通过

[f_n−1f_n−2]\begin{bmatrix} f\_{n-1}&f\_{n-2} \end{bmatrix}

转移到

[f_nf_n−1]\begin{bmatrix} f\_{n}&f\_{n-1} \end{bmatrix}

接下来考虑如何转移。

将 f_nf\_{n} 拆成 X×f_n−1−X×f_n−2X\times f\_{n-1}-X\times f\_{n-2} 的形式，又因为 f_n−1=xn−1+yn−1f\_{n-1}=x^{n-1}+y^{n-1}，f_n−2=xn−2+yn−2f\_{n-2}=x^{n-2}+y^{n-2}，代入得：

X×(xn−1+yn−1)−X×(xn−2+yn−2)X\times \left ( x^{n-1}+y^{n-1} \right ) -X\times \left ( x^{n-2}+y^{n-2} \right )

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

xn+yn=(x+y)×(xn−1+yn−1)−xy×(xn−2+yn−2)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=(x+y)×f_n−1−xy×f_n−2f\_{n}=\left ( x+y \right ) \times f\_{n-1}- xy \times f\_{n-2}

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

我们发现 f_1=b+d2+b−d2=bf\_{1}=\frac{b+\sqrt{d} }{2}+\frac{b-\sqrt{d} }{2}=b，f_2=(b+d2)2+(b−d2)2=b2+d2f\_{2}= \left ( \frac{b+\sqrt{d} }{2} \right )^{2}+ \left ( \frac{b-\sqrt{d} }{2} \right )^{2} = \frac{b^{2}+d }{2}。

bb 一定是整数，而由于 b mod 2=1b\bmod{2}=1，d mod 4=1d \bmod{4}=1，由费马小定理可得 b2≡b(mod2)b^{2}\equiv b \pmod{2}，所以 b2+d mod 2=0b^{2}+d \bmod{2}=0，所以 b2+d2\frac{b^{2}+d }{2} 也是整数。

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

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

综上，f_nf\_{n} 总为整数。

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

如下：

[b1 −b2−d40]\begin{bmatrix} b &1 \\\ -\frac{b^{2}-d}{4} &0\end{bmatrix}

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

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

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

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

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

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

因为 0<b2≤d0 < b^{2} \le d，所以 b−d2\frac{b-\sqrt{d} }{2} 一定小于 0。

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

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

综上，当且仅当 nn 为偶数且 b2≠db^{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 我