https://atcoder.jp/contests/arc113/tasks/arc113_e
给字符串,仅由a和b组成
操作: 任意选择两个相同的字母，把它们之间的内容 颠倒顺序，删掉这两个被选择的字母
你可以操作 0 到任意次
求字典序最大的结果
显然，可以把a看作0,b看作1,也就是1尽量靠前且尽量多，而在满足1尽量多的时候，让0也尽量多
显然 如果0有偶数个，可以不消耗任何1,让结果以1开始
如果以0结束，也同样可以不消耗任何1,让结果以1开始
…
那么就是如何分类是这个问题的关键，怎么尽量少的分化，覆盖所有情况。
比赛里做出的人不多，有些cf红名大佬都没出 XD
我在讨论时，从 起始字符，终止字符，字符个数，连续字符个数多个方面去分类，想也不用想，没写出来,(之讨论到了部分情况)
https://atcoder.jp/contests/arc112
初始 a=[1...n]
每次操作 把一个元素移动到开头或结尾
给定m次操作后得到的a
问 有多少个具体的方案 能得到目标的a mod 998244353
$n\in [2,3000]$
m 3000
2s
1024mb
m 只要大于等于n 就所有方案都可以
所以n的大小在这里更关键3000的话，难道要n^2左右的算法？
如果倒着来就是每次选开头或结尾的 插入到序列中任何位置
似乎没有变简单
如果把每个数字最后一次操作的时刻记录下来
对应到最后数组中的位置，一定是连续的
因为 最终数组 总可以 划分成 [左侧放入][未操作][右侧放入]， 每段长度可以为0
而对于单侧放入的，靠外的 最后一次操作时间 一定 晚于 靠内的
所以可以
dp[l][r][t] 表示 结果数组中[l..r] 这一段最后操作的时间为t的 到t时刻的方案数
初始状态
讨论一下 未操作的一段 如果非0， 首先一定要满足 单调递增，那么 这一段的对应dp[l][r][0]+=1
否则未操作的一段长度为0,那么首个停止的放入时 可以从左也可以从右
dp[l][l][t] += 2*(2n)^{t-1}, 前t-1随意操作，最后一次操作a[l]
然后转移
dp[l][r][t] => dp[l-1][r][t1], 要贡献，也就是(t+1..t1-1) 这一段随便操作，最后一次操作a[l-1]
dp[l-1][r][t1] += dp[l][r][t] * (2(n-(r-l+1)))^(t1-t-1) * 1
同理 从右侧加入
dp[l][r+1][t1] += dp[l][r][t] * (2(n-(r-l+1)))^(t1-t-1) * 1
ans = dp[1][n][m]
问题是状态是$O(n^2m)$的，而转移需要枚举$t_1$,所以时间是$O(n^2m^2)$的，会tle
一个观察是， 上面除了初始化和具体的l,r有关系，而后续的 似乎没关系，但实际上 受到边界的影响
$dp_{l,r,t,l<r,t>0}=\sum_{t_0 < t} dp_{l+1,r,t_0}(2(n-(r-l)))^{t-t_0-1}+dp_{l,r-1,t_0}(2(n-(r-l)))^{t-t_0-1}$
$\displaystyle dp_{l,r,t,l<r,t>0}=(2(n-(r-l)))^{t-1}\sum_{t_0 < t} \frac{dp_{l+1,r,t_0}+dp_{l,r-1,t_0}}{(2(n-(r-l)))^{t_0}}$
这样的话 可以前缀和，时间复杂度$O(n^3)$
再从贡献的角度来看，初始是[l,r,t]的情况
那么 每次到下一个状态 中间的任意的可选次数都是 每次-1， 与选左选右没有关系
$(2(n-(r-l+1)))^{t_0}(2(n-(r-l+1)-1))^{t_1}\cdots (2)^{t_{n-(r-l+1)}}$
而其中 有$(l-1)$次是 选左边，所以$\binom{n-(r-l+1)}{l-1}$ 个 与左右相关的顺序
然后 $t+\sum_{i=0}^{n-(r-l+1)} (t_i+1)= m$
而初始状态 只有 全操作过$l=r,t>0$和 有不动块$t=0$两种情况（注意重叠
所以 需要计算 $f(t,s)=(2(n-s))^{t_0}(2(n-s-1))^{t_1}\cdots (2)^{t_{n-s}},t+\sum_{i=0}^{n-s} (t_i+1)= m$
$ans = \sum_{p=1}^{n} \sum_{t=1}^{m} 2(2n)^{t-1}\binom{n-1}{p-1}f(t,1)+\sum_{l,r,a[l\cdots r]单增} \binom{n-(r-l+1)}{l-1}f(0,r-l+1)$
$f$看着有点怪，换个角度$f(t,s) = g(m-t,n-s)$
$g(t,s)=f(m-t,n-s)=(2(s))^{t_0}(2(s-1))^{t_1}\cdots (2)^{t_{s}},\sum_{i=0}^{s} (t_i+1)=t$
$ans = \sum_{p=1}^{n} \sum_{t=1}^{m} 2(2n)^{t-1}\binom{n-1}{p-1}g(m-t,n-1)+\sum_{l,r,a[l\cdots r]单增} \binom{n-(r-l+1)}{l-1}g(m-0,n-(r-l+1))$
$g(t,s)=\sum_{t_0=0}^{t-1}(2s)^{t_0} g(t-(t_0+1),s-1),\sum_{i=0}^{s} (t_i+1)=t$
$g(t,1) = 2^{t-1}$
令$g_s(x)=\sum_{t=1}^{\infty} g(t,s)x^t$, 即$[x^0]g_s(x)=0$
$[x^t]g_s(x) = \sum_{t_0=0}^{t-1}(2s)^{t_0} [x^{t-(t_0+1)}] g_{s-1}(x)$
$[x^t]h_s(x)=(2s)^{t_0}$
$[x^t]g_s(x) = \sum_{t_0=0}^{t-1} [x^t]h_s(x) [x^{t-(t_0+1)}] g_{s-1}(x)$
$g_s(x) = x h_s(x)g_{s-1}(x)$
$g_1(x)=\sum_{i=1}^{\infty} g(i,1)x^i=\sum_{i=1}^{\infty} 2^{i-1}x^i$
令$H_s(x)=xh_s(x)=x\sum_{i=0}^{\infty} (2s)^{i} x^i=\sum_{i=1}^{\infty} (2s)^{i-1} x^i$
注意到 $g_1(x)=H_1(x)$
$g_s(x)=\prod_{i=1}^{s} H_i(x)$
应该就过了
https://atcoder.jp/contests/arc111
一个查询问题
整数序列,a[n],初始全0,
ans = 0
q个询问，其中$v_i\in[0,M-1]$
ans+=(\sum a[l_i..r_i])最后输出ans
Maroon 觉得这个 问题太简单了
对于 给定$N,M,Q$,那么 有 $(\frac{N(N+1)}{2}(M+M+1))^Q$种合法的输入，求所有输出的值的和 mod 998244353
输入 $N,M,Q \in[1,200000]$
4s
1024mb
啊？？？？
题意上的 合法输入，左边就是选$[l,r]$, 右边就是min的选v,max的选v,输出的1
这个 询问的问题真的可做吗？感觉上 统计所有方案可以从概率频次的角度去计算，但是原来的单独问题真的能做吗？
比如 改成了
1 | 大小大小大小大小大小大小大小大 |
感觉做不了一点
回到本题，感觉就每个点单独考虑贡献就好了
对于 a[i] 表示$[x^v]f_{i,t}(x)$表示下标$i$经过$t$轮后值为$v$的操作方案数,初始状态有$[x^v]f_{i,0}(x) = [v=0]$
那么 就可以变成 当前状态+=上个状态 * 区间选择 * (操作类型=1)* 值选择
令$c_i=i(n+1-i)$表示一次选区间时$i$被选中的方案数，那么不被选中的为$\frac{n(n+1)}{2} - c_i$
$\mathrm{ans}=\sum_{i=1}^{N}c_i\sum_{v=0}^{M-1}v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$, 表示$t+1$次的时候覆盖了位置$i$调用输出$v$了，而注意后续任何操作该次贡献都翻倍，所以有后面的$A^{Q-(t+1)}$
这是一个 明显超时的方案，接下来就看能不能做效率优化了
令$A=\frac{N(N+1)}{2}(M+M+1) \neq 0$表示单次所有操作方案数
考虑$[x^v]f_{i,t}(x)$的来源
$[x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2}\cdot 1)$ 表示一个位置不被操作的方案数
$[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (M-v)$ 表示 使用$\min(v_1),v_1 \ge v$的方案数，也就是min操作后不影响
$\sum_{v_1 > v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$ 表示 使用$\min(v),v_1 > v$的方案数，min操作后改变
$[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (v+1)$ 表示 使用$\max(v_1),v_1 \le v$的方案数，也就是操作后不影响
$\sum_{v_1 < v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$ 表示 使用$\max(v),v_1 < v$的方案数，操作后改变
合并一下
$[x^v]f_{i,t}(x) = [x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2}\cdot 1)+[x^v]f_{i,t-1}(x) \cdot (c_i) \cdot (M+1) + \sum_{v_1 \neq v}[x^{v_1}]f_{i,t-1}(x) \cdot (c_i) \cdot 1$
$= [x^v]f_{i,t-1}(x) \cdot ((\frac{n(n+1)}{2} - c_i)\cdot (M+M)+\frac{n(n+1)}{2} +(c_i) \cdot (M)) + \sum_{v_1 = 0}^{M-1} [x^{v_1}]f_{i,t-1}(x) \cdot (c_i)$ , 从第二部分提取1个到第三部分
而右侧 是和v无关的，只和$t$相关，因为它是位置$i$的所有可能值的方案数，所以和$i$也是无关的，但$c_i$是有关$i$的
而左侧也和$v$无关，表现的是不同$v$之间没有直接的影响
$= [x^v]f_{i,t-1}(x) \cdot (\frac{n(n+1)}{2}(2M+1) - c_iM) + A^{t-1} \cdot c_i$
令$d_i=\frac{n(n+1)}{2}(2M+1) - c_iM$
$[x^v]f_{i,t}(x)= [x^v]f_{i,t-1}(x) \cdot d_i+ A^{t-1} \cdot c_i$
讨论$d_i = 0,A,$和其它（这里我的思考过程是3步骤，不过回过头看只用看是否是$A$
若$d_i=0$, $[x^v]f_{i,t}(x)= A^{t-1} \cdot c_i$
否则$d_i\neq 0$
$\displaystyle \frac{[x^v]f_{i,t}(x)}{d_i^t}= \frac{[x^v]f_{i,t-1}(x)}{(d_i)^{t-1}} + \frac{c_i}{d_i}(\frac{A}{d_i})^{t-1}$
$\displaystyle \frac{[x^v]f_{i,t}(x)}{d_i^t}= \frac{[x^v]f_{i,0}(x)}{(d_i)^{0}} + \frac{c_i}{d_i}\sum_{j=0}^{t-1} (\frac{A}{d_i})^{j}$
令$\displaystyle g(x,p)=\sum_{i=0}^{p-1} x^i$,有$x=1$时$g(x,p)=p$,当$x\neq 1$时$\displaystyle g(x,p)=\frac{x^p-1}{x-1}$
$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([x^v]f_{i,0}(x) + \frac{c_i}{d_i} g(\frac{A}{d_i},t)\right)$
$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([v=0] + \frac{c_i}{d_i} g(\frac{A}{d_i},t)\right)$,未操作时都是0
如果$d_i = A$则$\displaystyle [x^v]f_{i,t}(x)= d_i^t\left([v=0] + \frac{c_i}{d_i} g(1,t)\right)= d_i^t\left([v=0] + \frac{c_i}{d_i} t\right)$,未操作时都是0
否则$d_i\neq 0,d_i\neq A$, 待定系数法
$[x^v]f_{i,t}(x) + k_iA^t = d_i([x^v]f_{i,t-1}(x) + k_iA^{t-1})$
$d_ik_iA^{t-1}-k_iA^t=A^{t-1}c_i$
$d_ik_i-k_iA=c_i$, 因为$A\neq 0$
$\displaystyle k_i=\frac{c_i}{d_i-A}$ 这里分母非0
$[x^v]f_{i,t}(x) + k_iA^t = (d_i)^t([x^v]f_{i,0}(x) + k_iA^0)$
$[x^v]f_{i,t}(x) = (d_i)^t([x^v]f_{i,0}(x) + k_i)- k_iA^t$
$= (d_i)^t([v=0] + k_i)- k_iA^t$，未操作时都是0, 而这种情况对于$d_i=0$ 也成立，一定$0\neq A$,
所以 $[x^v]f_{i,t}(x) = \frac{c_i}{d_i-A} ((d_i)^t-A^t), v\neq 0$
$\displaystyle \mathrm{ans}=\sum_{i=1}^{N}c_i\sum_{v=0}^{M-1}v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$,带入 上面时分类讨论$d_i$与$A$是否相等
令$\mathrm{ans}i=c_i\sum{v=0}^{M-1} v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x)) A^{Q-(t+1)}= c_i\sum_{v=1}^{M-1} v\sum_{t=0}^{Q-1} ([x^v]f_{i,t}(x))A^{Q-(t+1)}$ 注意到$v=0$时不会贡献
则 $\displaystyle \mathrm{ans}=\sum_{i=1}^{N} ans_i$
对于 $d_i=A$
$\displaystyle \mathrm{ans}i=c_i\sum{v=1}^{M-1}v\sum_{t=0}^{Q-1} d_i^t\left([v=0] + \frac{c_i}{d_i} t \right)A^{Q-(t+1)}$
$\displaystyle =c_i\sum_{v=1}^{M-1}v\sum_{t=0}^{Q-1} A^t\left(\frac{c_i}{A} t\right)A^{Q-(t+1)}$
$\displaystyle =c_i^2A^{Q-2}\frac{M(M-1)}{2} \sum_{t=1}^{Q-1} t$
$\displaystyle =c_i^2A^{Q-2}\frac{M(M-1)}{2} \frac{Q(Q-1)}{2}$
若$d_i\neq A$
$\displaystyle \mathrm{ans}i=c_i\sum{v=0}^{M-1}v\sum_{t=0}^{Q-1} \left(\frac{c_i}{d_i-A} ((d_i)^t-A^t)\right)A^{Q-(t+1)}$
$\displaystyle =\frac{c_i^2}{d_i-A} A^{Q-1} \frac{M(M-1)}{2} \left(\sum_{t=0}^{Q-1} \left(\frac{d_i}{A}\right)^t-\sum_{t=0}^{Q-1} 1\right)$
$\displaystyle = \frac{c_i^2}{d_i-A} A^{Q-1}\frac{M(M-1)}{2} \left(g(\frac{d_i}{A},Q)-Q\right)$
整理一下,$N,M,Q$输入
$A=\frac{N(N+1)}{2}(M+M+1)\neq 0$
令$\displaystyle g(x,p)=\sum_{i=0}^{p-1} x^i$,有$x=1$时$g(x,p)=p$,当$x\neq 1$时$\displaystyle g(x,p)=\frac{x^p-1}{x-1}$
$c_i=i(n+1-i)$
$d_i=\frac{n(n+1)}{2}(2M+1) - c_iM$
$\displaystyle \mathrm{ans}=\sum_{i=1}^{N} ans_i$
若$d_i = A$, 则 $\displaystyle \mathrm{ans}_i=c_i^2A^{Q-2}\frac{M(M-1)}{2} \frac{Q(Q-1)}{2}$
若$d_i \neq A$,则$\displaystyle \mathrm{ans}_i = \frac{c_i^2}{d_i-A} A^{Q-1}\frac{M(M-1)}{2} \left(g(\frac{d_i}{A},Q)-Q\right)$
似乎就过了?
$A(x) = 1x + 1x^2 + 2x^3+ 3x^4+5x^5+8x^6+..$
已知$A(x)$(整数) 求问,x为有理数时$A(x)$的取值序列
$xA(x) = 1x^2 + 1x^3 + 2x^4+ 3x^5+5x^6+8x^7+..$
$(1-x)A(x) = x + 1x^3 + 1x^4 + 2x^5+ 3x^6+5x^7+8x^8+..$
$(1-x)A(x) = x + x^2A(x)$
$A(x)x^2 +(1+A(x))x - A(x) = 0$
$x = \frac{\sqrt{1+2A(x)+5A(x)^2}-1-A(x) }{2A(x)}$ (只考虑正的取值)
也就是找$1+2x+5x^2=y^2$ 的解
在pe 100 里面我们讨论过变形
$5+10+25x^2=5y^2$
$4+(1+5x)^2=5y^2$
$(1+5x)^2-5y^2=-4$
形式上是个pell方程右侧换成-4
在做过66和100以后，回顾看看
66是pell方程，解一定是渐进分数，且一定有解，所有解能由基础解的幂次生成
100是pell方程右侧改为-1的方程，解一定是渐进分数，但没有证明到一定有解(d=34时似乎真的没解)，通过连分数的递推寻找
这里
我们关心一下和佩尔方程的关系
在pe66，100中我们的步骤是这样的
$x^2-d y^2 = \pm 1$
$|\sqrt{d}-\frac{x}{y}| = |\frac{dy^2-x}{y^2(\sqrt{d}+\frac{x}{y})}| < \frac{1}{2y^2}$
然后满足上面不等式的一定是连分数的渐进分数
我们假设$x^2-dy^2 = c$
$\frac{x}{y} = \sqrt{d+\frac{c}{y^2}}$
上面式子的放缩部分是 $|\frac{c}{\sqrt{d}+\frac{x}{y}}| < \frac{1}{2}$
$ |\frac{4}{\sqrt{5}+\sqrt{5-\frac{4}{y^2} } }| < \frac{1}{2}$
当c比较大时 例如 $x^2-10y^2=9$ 有三组解答 $(7,2)…$, $(13,4)…$,$(57,18),…$
考虑两组满足 $x^2-5y^2=-4$的值
根据pe100的结论，$(9+4\sqrt{5})^n$ 是 其佩尔方程的基础解对应的值
$1=\frac{x_0^2-dy_0^2}{x_1^2-dy_1^2} $
$= \frac{x_0+y_0\sqrt{d}}{x_1+y_1\sqrt{d}} \cdot \frac{x_0-y_0\sqrt{d}}{x_1-y_1\sqrt{d}}$
$= \frac{(x_0+y_0\sqrt{d})(x_1-y_1\sqrt{d})}{-4} \cdot \frac{(x_0-y_0\sqrt{d})(x_1+y_1\sqrt{d})}{-4}$
$= ((\frac{x_0x_1-y_0y_1d}{4})+(\frac{x_1y_0-x_0y_1}{4})\sqrt{d})((\frac{x_0x_1-y_0y_1d}{4})-(\frac{x_1y_0-x_0y_1}{4})\sqrt{d})$
$= (\frac{x_0x_1-y_0y_1d}{4})^2-(\frac{x_1y_0-x_0y_1}{4})^2 d $
说明两个不同的-4的解, 如果能让$x_1y_0-x_0y_1 = 0 (\pmod 4)$,那么它们之间一定是通过乘一个=1的解得到的,(之考虑y是因为如果y为整数且等式成立，那么x必为整数),也就是它们有同样的基础解
如果y是偶数，$y = 2k$,显然 x也是2的倍数，直接解 $(2x)^2-5(2y)^2=-4$,$x^2-5y^2=-1$ 解之即可
如果y是奇数, x也是奇数
根据mod 4进行分类
$(4k_0+1,4k_1+1) ,(4k_0+3,4k_1+3)$ 有同样的基础解(如果有解)
$(4k_0+1,4k_1+3) ,(4k_0+3,4k_1+1)$ 有同样的基础解(如果有解)
所以最后分为3类
注意到基础解的幂次可乘性, 考虑(x,y)为最小全正解，$x>0,y>0$
$(x+y\sqrt{5})(9+4\sqrt{5})^{-1} = (x+y\sqrt{5})(9-4\sqrt{5})$
$ = ((9x-20y)+(9y-4x)\sqrt{5})$ , 因为是最小正解，所以再次乘积后 $9x-20y < 0$ 或 $9y-4x<0$
$ \frac{x}{y} < \frac{20}{9} 或 \frac{x}{y} > \frac{9}{4}$
$ \sqrt{5-\frac{4}{y^2}} < \frac{20}{9} 或 \sqrt{5-\frac{4}{y^2}} > \frac{9}{4}$
$\frac{2}{\sqrt{5}} \le y < \frac{18}{\sqrt{5}} 约 8.049844718999243 $
要尝试的y有限
综上原题可解
尝试8以内
1 | def isSquare(v): |
运行得到基础解
1 | 1 1 |
1 |
|
https://math.stackexchange.com/questions/742181/find-all-integer-solutions-for-the-equation-5x2-y2-4
https://math.stackexchange.com/questions/1088277/fermats-difference-equation-pells-equation
就过程进行书写,去掉自己尝试思考的中间步骤,只留下有效的过程
https://projecteuler.net/problem=66
$d = 1\to 1000$,d是非平方数
对于每个$d$ 求最小的正整数$x$使得$x^2-dy^2=1$,其中$x$,$y$都是正整数,
最后对所有这些$x$求最大的$x$
本文针对给定的$d$讨论具体的方程解法
抽屉原理
二元一次方程
绝对值
有理数/无理数
模运算
矩阵运算
数列/递推数列
二项式展开
反证法
归纳法
不等式(缩放,三角不等式)
共轭实数(不太知道怎么翻译比较好,还是对偶实数？ 描述的就是$a+b\sqrt{m}$与$a-b\sqrt{m}$
取任意正整数$q_0 > 1$
把区间$[0,1)$均分为$q_0$个左闭右开的区间,则每部分长度为$\frac 1{q_0}$, 考虑 $t \sqrt{d}$的小数部分($t = 0,\cdots,q_0$ 共计$q_0+1$个),抽屉原理,必定有两个落在同一区间, 即存在$0\leq i < j\leq q_0$使得 $| \{i \sqrt{d}\} - \{j \sqrt{d}\} | <\frac 1{q_0}$
即$|x-(j-i)\sqrt{d}| = | \{i \sqrt{d}\} - \{ j \sqrt{d}\} | < \frac 1{q_0} \leq \frac 1{j - i}$, 其中$x$用于去掉整数部分
这里要注意的是知道$i < j$,和它们的小数部分落在同一个区间,所以这里应该是它们的小数部分相减的绝对值,而不是相减的绝对值的小数部分,例如q取2, 一个取0.4,一个1.3,它们都在[0,0.5)的区间里,但是如果$|1.3-0.4|$ 再取绝对值的小数部分,得到的是0.9而不是0.1,对于x来说,只要增减1就能在最终的值上切换成功.
得到一个解$(x,y=j-i)$
取$\frac 1{q_1} < |x-(j-i)\sqrt{d}|$
如下这样, 相同的$(x,y)$一定是等于关系, 因此如下这样可以产生无限多的解
$|x_3-y_3\sqrt{d}| <\frac 1{q_3} < |x_2-y_2 \sqrt{d}| < \frac 1{q_2} < |x_1-y_1\sqrt{d}| <\frac 1{q_1} < |x_0-y_0 \sqrt{d}| < \frac 1{q_0} < 1$
对于上一个结论中的无限多个解
$0 < \left|x^2-dy^2\right| $
$=\left|x+y\sqrt{d}\right|\cdot\left|x-y\sqrt{d}\right|$
$=\left|x-y\sqrt{d}+2y\sqrt{d}\right|\cdot\left|x-y\sqrt{d}\right| $
$\le (\left|x-y\sqrt{d}\right|+\left|2y\sqrt{d}\right|)\cdot\left|x-y\sqrt{d}\right| $
$< \left(2y\sqrt{d}+\frac{1}{y}\right)\cdot\frac{1}{y}$
$\le 2\sqrt{d}+\frac 1{y^2} $
$\le 2 \sqrt{d} + 1 $
说明这无限多个$(x,y)$的取值,对$|x^2-dy^2|$的计算结果是有限范围内的整数
如果你看下面我提供的youtube链接,你会发现证明的细节步骤会有些差别,视频里,并没有这么精细的放缩,因为最终目的只需要证明有限个取值,而在中间直接放缩到 $\le |3y\sqrt{d}|$
抽屉原理,存在正整数$k$, 使得$|x^2-dy^2|=k$ 的 解有无限个
考虑这些解$(x \bmod k,y \bmod k)$ , 结果的方案数$\leq k^2$,也是有限的,
抽屉原理,存在$(M_x,M_y)$,有无限个$i$ 满足 $(x_i \bmod k, y_i \bmod k) = (M_x,M_y)$,在这无限组中取两组$(x_1,y_1),(x_2,y_2)$
令 $X=|\frac{x_1x_2-y_1y_2d}{k}|,Y=|\frac{x_2y_1-x_1y_2}{k}|$
有 $X^2-d \cdot Y^2 = \frac{(x_1^2-d \cdot y_1^2)(x_2^2-d \cdot y_2^2)}{k^2} = 1$
因为 $(x_2y_1-x_1y_2)\bmod k = (x_1y_1-x_1y_1) \bmod k = 0 \bmod k = 0$,所以$Y$是非负整数
注意到 $x^2-dy^2$ 的取值范围为 $\pm k$ (2个,有限个),但可取的$(x,y)$有无限对,抽屉原理,因此存在$(x_i,y_i)\neq(x_j,y_j)$使得 $x_i^2-dy_i^2=x_j^2-dy_j^2$ 这时 $\frac{x_i}{y_i} \neq \frac{x_j}{y_j}$ (否则代入前式子得到$x_i=x_j$), 即$Y$为非$0$正整数
因为$X$是有理数且满足pell方程,所以它是整数, 且$X = \sqrt{1+dY^2} \neq 0$
综上, 一定存在解
注,上面X,Y的等式看着很突兀,但在看了Youtube视频之后意识到了, 既然 基础解的幂次能有效,且证明了负幂次也有效,那么 $ x^2-dy^2 = 1 = k/k = \frac{x_1^2-dy_1^2}{x_2^2-dy_2^2}$ 然后通分化简就有了上面那个显得突兀的
令
如果解存在 $x,y \ge 0$
若$(x_0,y_0),(x_1,y_1)$ 是 $x^2-d y^2=1$ 的解
$1 = (x_0^2-d y_0^2)(x_1^2-d y_1^2)$
$= (x_0 + \sqrt{d} y_0)(x_0 - \sqrt{d} y_0)(x_1 + \sqrt{d} y_1)(x_1 - \sqrt{d} y_1)$
$= (x_0 + \sqrt{d} y_0)(x_1 + \sqrt{d} y_1)(x_0 - \sqrt{d} y_0)(x_1 - \sqrt{d} y_1)$
$= (x_0x_1 + dy_0 y_1 + \sqrt{d} (y_0x_1+y_1 x_0))(x_0x_1 + dy_0 y_1 - \sqrt{d} (y_0x_1+y_1x_0))$
$= (x_0x_1 + dy_0 y_1)^2 - d(y_0x_1+y_1 x_0)^2$
那么$(x_0x_1 + dy_0y_1, y_0x_1+y_1x_0)$也是一个解
如果定义 $A(x,y) = x+\sqrt{d}y,x > 0,y > 0$ 为一个解, 那么有 $A(x_0x_1 + dy_0 y_1,y_0x_1+y_1 x_0) = A(x_0,y_0)\cdot A(x_1,y_1)$
下面证明所有解都是最小解生成的
反证法, 因为$y$越大$x$越大, 设$(x_1,y_1)$为最小解, $(x_k,y_k)$不是由最小解,通过上述乘积的幂次方法生成的一个解
根据$y$越大$x$越大的性质,存在一个整数$n$
$(x_1+y_1 \sqrt{d})^n < (x_k+y_k \sqrt{d}) < (x_1+y_1 \sqrt{d})^{n+1} $, 同时乘$(x_1-y_1 \sqrt{d})^n$有
$1 < (x_k+y_k \sqrt{d}) (x_1-y_1 \sqrt{d})^n < (x_1+y_1 \sqrt{d}) $
注意到中间的表达式 也是一个解(且因为 它 大于1, 所以它的共轭 在0到1之间, 而它和它的共轭 只有 y的符号不同, 所以它的x和y的符号均为正)
这与最小解定义矛盾,所以所有解都是最小解生成的
关于pell方程的解 ,现在有了两个结论
下面开始看看连分数。
形如
$\alpha = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cfrac{1}{\ddots,}}}} $
例如
$ \sqrt{2} = 1 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \cfrac{1}{2 + \ddots}}}}}} $
展开的剩余部分是在[0,1)之间
证明：如果一个数是有理数,把它写成分数的形式,再按照连分数的方式展开,你会发现这过程就是辗转相除,分子分母单调递减 所以一定有限,它的逆否命题就是要证明的性质
渐进分数,把上述表示无理数$\alpha$的连分数部分截断所得到的分数
若$h,k$分别为渐进分数的分子和分母,根据简化为分数的过程
$\begin{bmatrix} h_n & k_n \end{bmatrix} = \begin{bmatrix} 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
然而这不好建立递推关系,稍做变形
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \cdot \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} a_{n-1} & 1 \\ 1 & 0 \end{bmatrix} \cdots \begin{bmatrix} a_0 & 1 \\ 1 & 0 \end{bmatrix} $
$\begin{bmatrix} h_n & k_n \\ ? & ? \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ ? & ? \end{bmatrix} $
左式的底部可以确定
$\begin{bmatrix} h_n & k_n \\ h_{n-1} & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ ? & ? \end{bmatrix} $
又因为递推关系,右边式子相当于左式带入n-1
$\begin{bmatrix} h_n & k_n \\ h_{n-1} & k_{n-1} \end{bmatrix} = \begin{bmatrix} a_n & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} h_{n-1} & k_{n-1} \\ h_{n-2} & k_{n-2} \end{bmatrix} $
综上
$h_n = a_n \cdot h_{n-1} + h_{n-2}$
$k_n = a_n \cdot k_{n-1} + k_{n-2}$
渐进值 $\frac{h_n}{k_n} = \frac{a_n \cdot h_{n-1} + h_{n-2}}{a_n \cdot k_{n-1} + k_{n-2}}$
且根据计算过程,可知 $h_n,k_n$互质
由上面的递推关系再递推有
$k_nh_{n-1}-k_{n-1}h_n=-(k_{n-1}h_{n-2}-k_{n-2}h_{n-1})=(-1)^n $,
$k_nh_{n-2}-k_{n-2}h_n=a_n(k_{n-1}h_{n-2}-k_{n-2}h_{n-1})=a_n(-1)^{n-1} $,
设无理数$\alpha$ 的精确表示为$[a_0,a_1,\cdots,a_n,x_{n+1}]$,即是最后$a_{n+1}$替换为精确的非整数值$x_{n+1}$,有$1\leq a_{n+1}<x_{n+1}<a_{n+1}+1,(n>=1)$
根据上方计算渐进值得到的公式,同理递推式有
$\alpha =\frac{x_{n+1}h_n+h_{n-1}}{x_{n+1}k_n+k_{n-1}} $
$\alpha - \frac{h_n}{k_n} =\frac{x_{n+1}h_n+h_{n-1}}{x_{n+1}k_n+k_{n-1}} -\frac{h_n}{k_n} $
$=\frac{h_{n-1}k_{n}-h_nk_{n-1}}{k_n(x_{n+1}k_n+k_{n-1})}$
$=\frac{(-1)^n}{k_n(x_{n+1}k_n+k_{n-1})}$
$|\alpha -\frac{h_n}{k_n}| =\frac{1}{k_n(x_{n+1}k_n+k_{n-1})} < \frac{1}{k_n(a_{n+1}k_n+k_{n-1})} = \frac{1}{k_nk_{n+1}}$
注意到$k_n$的递推式,容易发现它是单调递增的正整数,所以渐进分数真的是趋近($n$趋于无限大, 渐进分数与原无理数距离趋近于0)
$|k_n\alpha - h_n|$单调递减
证明:
$|k_n\alpha - h_n| - |k_{n-1}\alpha - h_{n-1}|$
$ = |k_n(\alpha - \frac{h_n}{k_n})| - |k_{n-1}(\alpha - \frac{h_{n-1}}{k_{n-1}})|$
$ = \frac 1{x_{n+1}k_n+k_{n-1}} - \frac 1{x_{n}k_{n-1}+k_{n-2}} $
$ = \frac {(x_{n}k_{n-1}+k_{n-2})-(x_{n+1}k_n+k_{n-1})}{(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {((a_n+\frac 1{x_{n+1}})k_{n-1}+k_{n-2})-(x_{n+1}k_n+k_{n-1})}{(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(x_{n+1}(a_nk_{n-1}+k_{n-2})+k_{n-1})-x_{n+1}(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(x_{n+1}k_n+k_{n-1})-x_{n+1}(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})}$
$ = \frac {(1-x_{n+1})(x_{n+1}k_n+k_{n-1})}{x_{n+1}(x_{n+1}k_n+k_{n-1})(x_{n}k_{n-1}+k_{n-2})} < 0$
由此也可知和原无理数的距离$|\alpha - \frac{h_n}{k_n}|$单调递减
$|\alpha - \frac{h_n}{k_n}|-|\alpha -\frac{h_{n-1}}{k_{n-1}}|$
$=\frac {|{k_n}\alpha-{h_n}|-\frac {k_n}{k_{n-1}}|{k_{n-1}}\alpha-{h_{n-1}}|}{k_n}$ (因为$k_n$单调递增
$<\frac {|{k_n}\alpha-{h_n}|-|{k_{n-1}}\alpha-{h_{n-1}}|}{k_n} < 0$
https://proofwiki.org/wiki/Convergents_are_Best_Approximations
若$(h_n,k_n)$是一个渐进分数,则对于分母$k_n$,分子取$h_n$时,整个分数最接近原无理数
取任意$h\neq h_n$,根据三角不等式
$|\alpha -\frac{h}{k_n}| \geq |\frac{h-h_n}{k_n}| - |\alpha - \frac{h_n}{k_n}|$
$>\frac 1{k_n} - \frac 1{k_nk_{n+1}} $,因为n足够大 $k_{n+1}>=3$有
$> \frac 1{k_n} - \frac 1{2k_n} $
$=\frac 1{2k_n} $
$> \frac 1{k_nk_{n+1}} > |\alpha -\frac{h_n}{k_n}|$
证明了$h_n$是最接近的分子
即 $|k_n\alpha - h|$在 $h=h_n$时取最小值
考虑任意$(h,k),(0 < k < k_n)$,且$\frac hk$的为最简分数, 且不是渐进数
若它不是最简分数, 则它是它最简分数的t倍, 比它最简分数得到的值更大
因为已经证明了渐进数随着$n$增大, $|k_n\alpha - h_n|$单调递减,且渐进数分子分母互质,所以如果是渐进数则对应渐进数的该表达式 更大
设二元一次方程组
$h_nx+h_{n-1}y=h$
$k_nx+k_{n-1}y=k$
则有$(x,y)=(\frac {hk_{n-1}-kh_{n-1}}{h_nk_{n-1}-h_{n-1}k_n},\frac {hk_{n}-kh_{n}}{h_nk_{n-1}-h_{n-1}k_n}) = ((-1)^{n-1}(hk_{n-1}-kh_{n-1}),(-1)^{n-1}(hk_{n}-kh_{n}))$
因为$\frac hk$不是渐进分数,所以$x,y$都是非零整数,又因为$k < k_n$和$k_nx+k_{n-1}y=k$有:$x,y$异号
因为$\alpha - \frac {h_n}{k_n} =\frac{(-1)^n}{k_n(x_{n+1}k_n+k_{n-1})}$的分子为$(-1)^n$,分母为正数,
所以$\alpha - \frac {h_n}{k_n}$和$\alpha - \frac {h_{n-1}}{k_{n-1}}$异号
即$k_n\alpha - {h_n}$和$k_{n-1}\alpha - {h_{n-1}}$异号
有$x(k_n\alpha - {h_n})$和$y(k_{n-1}\alpha - {h_{n-1}})$同号
$|k\alpha -h| = |(k_nx+k_{n-1}y)\alpha - (h_nx+h_{n-1}y)|$
$= |x(k_n\alpha - {h_n}) + y(k_{n-1}\alpha - {h_{n-1}})|$,因为同号
$= |x(k_n\alpha - {h_n})|+|y(k_{n-1}\alpha - {h_{n-1}})|$,因为$x,y$非零整数:
$|k\alpha - h| > |k_n\alpha - {h_n}|$且$|k\alpha -h|>|k_{n-1}\alpha - {h_{n-1}}|$, 得证
https://proofwiki.org/wiki/Condition_for_Rational_to_be_a_Convergent
反证法, 证明:
假设都不满足,有
$0 \leq |\alpha-\frac{h_{n+1}}{k_{n+1}}| - \frac{1}{2k_{n+1}^2} + |\alpha-\frac{h_{n}}{k_{n}}|-\frac{1}{2k_{n}^2}$, 因为$\alpha - \frac{h_{n}}{k_{n}} =\frac{(-1)^n}{k_n(x_{n+1}k_n+k_{n-1})}$正负交替,所以
$ = |\frac{h_{n+1}}{k_{n+1}}-\frac{h_{n}}{k_{n}}|-\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = |\frac{h_{n+1}k_{n}-h_{n}k_{n+1}}{k_{n+1}k_{n}}|-\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = \frac 1{k_nk_{n+1}} -\frac 1{2k_{n+1}^2} -\frac 1{2k_{n}^2}$
$ = \frac {-(k_n-k_{n+1})^2}{2k_{n}^2k_{n+1}^2} < 0$
矛盾, 因此至少有一个满足, 得证
证明
设$\frac hk$满足不等式$|\alpha - \frac hk|<\frac 1{2k^2}$,则存在$n$使得渐进数分母满足 $k_{n+1} > k \ge k_n $, 若$\frac hk \neq \frac{h_n}{k_n}$,即$k_n < k$
$0 \leq \frac{|hk_n-h_nk|-1}{kk_n}$
$= |\frac{h}{k}-\frac{h_n}{k_n}|-\frac{1}{kk_n}$,因为三角不等式,有
$\leq |\alpha -\frac{h}{k}|+|\alpha -\frac{h_n}{k_n}|-\frac{1}{kk_n}$, 因为假设满足的不等式
$< \frac 1{2k^2} + \frac 1{k_n}|k_n\alpha - h_n|-\frac{1}{kk_n}$,因为上面的最优接近, 所有$< k_{n+1}$ 的分母中 都大于 $(h_n,k_n)$的方案
$< \frac 1{2k^2} + \frac 1{k_n}|k\alpha - h|-\frac{1}{kk_n}$
$= \frac 1{2k^2} + \frac {k}{k_n}|\alpha - \frac hk|-\frac{1}{kk_n}$因为假设满足的不等式
$< \frac 1{2k^2} + \frac {k}{k_n}\cdot \frac 1{2k^2}-\frac{1}{kk_n}$
$= \frac {k_n-k}{2k^2k_n} < 0$
矛盾,因此$\frac hk$和某个渐进数相等
注记：最开始该文的版本,的渐进分数的部分直接使用的是pell方程中$\sqrt{d}$,其中$d$是非平方正整数,但为了写project euler 100需要的证明,需要把它扩充到实数（当然也是成立的）,所以这部分改写了一次
quadratic irrational(二次无理数) 定义: 二次整式多项式的根 $\frac{-b\pm \sqrt{b^2-4ac}}{2a}$ 或者形如$\frac{P+\sqrt{D}}{Q}$
一个无理数是二次无理数, 当且仅当它的连分数是循环连分数: An irrational number is quadratic irrational if and only if its continued fraction is periodic.
按照连分数的写法,令循环节的值为$t$
还原为分数,有$x=\frac{a t + b}{c t +d},t = \frac{et+f}{gt+h}$ 变换左表达式用$x$表示$t$,带入右侧表达式得到$\frac{ix+j}{kx+l} = \frac{mx+n}{ox+p}$,其中字母$a \to p$均为整数,且注意到$x$为无理数, 所以化简后一定是二次方程
定义,对于无理数x
$f(x) = x-1 (x>1)$
$f(x) = \frac{1}{\frac{1}{x}-1} , (x<1)$
对应到连分数展开$[a_0,a_1,a_2,\cdots]$,即是将首个数字减少$1$,($x>1$时就是$a_0$减去$1$,$x<1$时就是$a_1$减去$1$)
令$x_1=x,x_{n+1}=f(x_n)$,可以知道 这是一个无限数列
如果$x$满足$ax^2+bx+c=0$,写作$x \in g(a,b,c)$
那么$x-1$ 满足$a(x-1)^2+(2a+b)(x-1)+(a+b+c) = ax^2+bx+c=0$, 即$x-1 \in g(a,2a+b,a+b+c)$
那么$\frac{1}{\frac{1}{x}-1} = \frac{x}{1-x}$ 满足$(a+b+c)(\frac{x}{1-x})^2+(b+2c)\frac{x}{1-x}+c = \frac{ax^2+bx+c}{(1-x)^2} = 0$, 即$\frac{1}{\frac{1}{x}-1} \in g(a+b+c,b+2c,c)$
所以$f(x)$满足 $f(x)\in g(a,2a+b,a+b+c)$ 或 $f(x)\in g(a+b+c,b+2c,c)$
不失一般性,写作$x_n \in g(s_n,t_n,u_n)$,有 $s_n > 0$, 否则把三元组同时换号
注意到上式 $(2a+b)^2-4a(a+b+c)=b^2-4ac=(b+2c)^2-4(a+b+c)c$
说明了 $t_n^2-4s_nu_n$是和$n$无关的值
反证法: 如果只有有限个$u<0$,那么从某一处开始,$s>0,u>0$且$t<0$(因为 $x > 0$)
那么意味着 $t$ 严格单调递增,(因为$t$的变化关系是$t=2s+t$或$t=t+2u$),整数是离散的,矛盾
所以有无限个$u_n<0$, 即无限多$s_n u_n < 0$
注意到 $t_n^2-4s_nu_n$是常数,抽屉原理, 至少有一个三元组$[s_n,t_n,u_n]$ 出现了三次以上,一个二次方程有两个解,所以有满足的$x_n=x_m,m>n$
得证 连分数展开有循环
Theorem 1. If x is a positive quadratic irrational then its continued fraction is eventually periodic.
https://proofwiki.org/wiki/Definition:Quadratic_Irrational/Reduced
Definition 1.24. $x$ 是二次方程的一个根,$\overline{x}$ 是另一个根,那么如果 $x > 1$ 且 $-1 < \overline{x} < 0$.那么称 x 为 reduced
Theorem 1.25. (Galois’ Theorem) 无理数a. a是纯循环连分数（从$a_0$开始的循环节）,当且仅当 x is reduced. If $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ and $\overline{x}$ 是它共轭实数, then $-\frac{1}{x} = [\overline{a_{l−1}, . . . , a_2, a_1}].$
设reduced二次无理数$x$的一个渐进分数为$[a_0,a_1,\cdots,a_n], x>1,-1<\overline{x}<0$
那么有 $x_{n+1}=\frac{1}{x_n-a_n}$ 表示 按照展开从n处向后取值
$\overline{x_{n+1}} = \frac{1}{\overline{x_n-a_n}} = \frac{1}{\overline{x_n}-a_n}$,(因为 两个形如$A+B\sqrt{C}$的无理数相乘为有理数,说明相乘后的无理数的系数为0,所以更改其中一个无理数的系数的正负,另一个无理数系数的正负更改即可)
注意到$x \ge 1$有$a_0 \ge 1$,所以 $a_n \ge 1$
下面归纳证明 $-1 < \overline{x_n} < 0 $
若 $-1 < \overline{x_n} < 0$
有 $\frac{1}{\overline{x_{n+1}}} = \overline{x_n} - a_n < -1$
即 $-1 < \overline{x_{n+1}} < 0$,得证
$-1 < \overline{x_n} = \frac{1}{\overline{x_{n+1}}}+a_n < 0$
$ 1 > -\frac{1}{\overline{x_{n+1}}}-a_n > 0$
$ a_n = [ -\frac{1}{\overline{x_{n+1}}} ] $ ($a_n$等于分式的整数部分)
因为上面已经证明 如果是二次无理数,那么必定有循环节,所以存在$x_i = x_j,(i < j )$
即$\overline{x_i}=\overline{x_j}$
即$a_{i-1}=[-\frac{1}{\overline{x_i}}]=[-\frac{1}{\overline{x_j}}] = a_{j-1}$
即$x_{i-1}=a_{i-1}+\frac{1}{x_i} = a_{j-1}+\frac{1}{x_j} = x_{j-1}$, 意义就是如果两个后缀相等,那么它们各向前一个 也相等,综上逐步迭代$a_0 =a_{j-i}$
因此证明了 如果一个二次无理数是 reduced,那么它是个纯循环连分数
首先有循环节的连分数一定是二次无理数（上面证过了)
因为是纯循环,所以$a_0 \ge 1$,所以$a_n \ge 1$,有$x > 1$
假设周期为$n$, 有 $x_n = x = [\overline{a_0,a_1,\cdots,a_{n-1}}]$
根据上面推过的递推式 $x = \frac{x_nh_{n-1}+h_{n-2}}{x_nk_{n-1}+k_{n-2}} = \frac{xh_{n-1}+h_{n-2}}{xk_{n-1}+k_{n-2}}$
化简 $k_{n-1}x^2+(k_{n-2}-h_{n-1})x-h_{n-2}=0$
下面证明这个方程除了$x$ (已经有 $x>1$了)的另一个根$\overline{x}$满足$-1 < \overline{x} < 0$
连续函数零点存在性定理
$x = 0$时 原式子 $=-h_{n-2} < 0$
$x = 1$时 原式子
$= k_{n-1}+(h_{n-1}-k_{n-2})-h_{n-2}$
$= (a_{n-1}k_{n-2}+k_{n-3}) + (a_{n-1}h_{n-2}+h_{n-3}) -k_{n-2}-h_{n-2}$
$= (a_{n-1}-1)(h_{n-2}+k_{n-2}) + (h_{n-3}+k_{n-3}) $
$ > 0 $
说明了另一个根$-1 < \overline{x} < 0$
至此证明了 reduced 和 纯循环之间的 充要
若 $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ 且 $\overline{x}$ 是它共轭实数, 有 $-\frac{1}{\overline{x}} = [\overline{a_{l−1}, . . . , a_2, a_1,a_0}].$
考虑有限的连分数 $x = [a_0,a_1,\cdots,,a_n], y=[a_n,a_{n-1},\cdots,a_0] , a_i > 0$
$h_n,k_n$为$x$的分子分母,$h_n’,k_n’$为$y$的分子分母
要证明 $\frac{h_n}{h_{n-1}} = \frac{h_n’}{k_n’}$ 且 $\frac{k_n}{k_{n-1}} = \frac{h_{n-1}’}{k_{n-1}’}, n \ge 1$ 且分子分母对应相等(因为是最简分数,所以只要证明了分数相等就有对应相等了)
注意到上面 $h_n = a_n \cdot h_{n-1} + h_{n-2}$,同时除以 $h_{n-1}$
$\frac{h_n}{h_{n-1}} = a_n + \frac{1}{\frac{h_{n-1}}{h_{n-2}}}$
递归展开 可以得到 $\frac{h_n}{h_{n-1}} = [a_n,a_{n-1},\cdots,a_0]$,
注意到 $k_n = a_n \cdot k_{n-1} + k_{n-2}$,同理 $\frac{k_n}{k_{n-1}} = [a_n,a_{n-1},\cdots,a_1] $(注意是$a_1$不是$a_0$)
根据上面的递归展开的结论 和 y的分子分母定义 有
$\frac{h_{n}}{h_{n-1}} = [a_{n},a_{n-1},\cdots,a_0] = \frac{h_{n}’}{k_{n}’}$
$\frac{k_{n}}{k_{n-1}} = [a_{n},a_{n-1},\cdots,a_1] = \frac{h_{n-1}’}{k_{n-1}’}$
且分子分母对应相等(因为是最简分数)
若$x$是纯循环连分数,则$x$为reduced 二次无理数,则$-\frac{1}{\overline{x}}$为reduced的二次无理数,则$-\frac{1}{\overline{x}}$为纯循环连分数
假设直接取$n+1 = $ 两个循环节长度的最小公倍数
$k_{n}x^2+(k_{n-1}-h_{n})x-h_{n-1}=0$
令
$y = [\overline{a_n,a_{n-1},\cdots,a_0}] = [a_n,a_{n-1},\cdots,a_0,y]$
$y = \frac{h_n’y+h_{n-1}’}{k_n’y+k_{n-1}’}$
上面证明了对应相等$h_n=h_n’,k_{n-1}=k_{n-1}’, h_{n-1}=k_{n}’,h_{n-1}’=k_n$
做对应替换,$y = \frac{h_ny+k_{n}}{h_{n-1}y+k_{n-1}}$
展开 $k_{n}{(-\frac{1}{y})}^2+(k_{n-1}-h_{n})(-\frac{1}{y})-h_{n-1}=0$
$-\frac{1}{y} = \overline{x}$ 得证($y$为正 所以 不可能等于$x$)
至此 Theorem 1.25. (Galois’ Theorem) 无理数a. a是纯循环连分数（从a0开始的循环节）,当且仅当 x is reduced. If $x = [\overline{a_0, a_1, a_2, . . . , a_{l−1}}]$ and $\overline{x}$ 是它共轭实数, then $-\frac{1}{\overline{x}} = [\overline{a_{l−1}, . . . , a_1, a_0}].$ 得证
Theorem 1.26 $d$是非平方数,那么$\sqrt{d} = [\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,\cdots,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
也就是 是从第二位开始循环节,且循环节最后一个是它的整部的2倍,且剩余部分是回文
令$x=\lfloor \sqrt{d} \rfloor + \sqrt{d}$ 则$\overline{x} = \lfloor \sqrt{d} \rfloor - \sqrt{d}$
注意它们的取值范围发现$x$是reduced 二次无理数
因此 $ x = \lfloor \sqrt{d} \rfloor + \sqrt{d} = [\overline{2\lfloor \sqrt{d} \rfloor,a_1,a_2,\cdots,a_{l-1}}]$
$ = [2\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,\cdots,a_{l-1},2\lfloor \sqrt{d} \rfloor}]$
$ \sqrt{d}= [\lfloor \sqrt{d} \rfloor,\overline{a_1,a_2,\cdots,a_{l-1},2\lfloor \sqrt{d} \rfloor}]$
根据Galois’ Theorem有
$\frac{1}{\sqrt{d}-\lfloor \sqrt{d} \rfloor} = -\frac{1}{\overline{x}} = [\overline{a_{l-1},\cdots,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
也就是$\sqrt{d} = [\lfloor \sqrt{d} \rfloor,\frac{1}{\sqrt{d}-\lfloor \sqrt{d} \rfloor}]$
$ = [\lfloor \sqrt{d} \rfloor,\overline{a_{l-1},\cdots,a_2,a_1,2\lfloor \sqrt{d} \rfloor}]$
因此 循环内容 和 回文性质 得证
因为平方带来的对称性,只考虑$x>0,y>0$的解
若$d$为非平方数,$x=\sqrt{d}$,
则对于任意$n$,存在整数$P_n,Q_n$满足$x_n=\frac{P_n+\sqrt{d}}{Q_n}$和$d-P_n^2 = 0 \pmod{Q_n}$
当$n=0$时$(P_0,Q_0) = (0,1)$满足,归纳法,若$n$时能满足上述两点性质,则
$x_{n+1} = \frac{1}{x_n-a_n}$
$=\frac{1}{\frac{P_n+\sqrt{d}}{Q_n}-a_n}$
$=\frac{Q_n}{P_n+\sqrt{d}-a_n{Q_n}}$ (通过分母有理化)
$=\frac{Q_n(P_n-a_nQ_n-\sqrt{d})}{(P_n-a_nQ_n)^2-d}$
$=\frac{a_nQ_n-P_n+\sqrt{d}}{\frac{d-(P_n-a_nQ_n)^2}{Q_n}}$
$(P_{n+1},Q_{n+1}) = (a_nQ_n-P_n,\frac{d-(P_n-a_nQ_n)^2}{Q_n})$
现在要证明的就是 它是满足$\frac{P_{n+1}+\sqrt{d}}{Q_{n+1}}$的形式,并且满足上面的取模
也就是要证明$Q_{n+1}$是整数
$Q_{n+1} = \frac{d-P_n^2}{Q_n}+2a_nP_n-a_n^2Q_n$, 因为$n$时有 $d-P_n^2 = 0 \pmod{Q_n}$所以 $Q_{n+1}$是整数
又因为$Q_nQ_{n+1}=d-P_{n+1}^2$ 所以 $d-P_{n+1}^2 = 0 \pmod{Q_{n+1}}$ 得证
对于$n \ge 2$ 要证明 $h_{n-1}^2-d k_{n-1}^2=(-1)^n Q_n$
证明:
$\sqrt{d} = \frac{x_n h_{n-1}+h_{n-2}}{x_nk_{n-1}+k_{n-2}}$
把$ x_n = \frac{P_n+\sqrt{d}}{Q_n}$带入并通分化简
$(P_nk_{n-1}+Q_nk_{n-2}-h_{n-1})\sqrt{d} = P_nh_{n-1}+h_{n-2}Q_n-k_{n-1}d$, 无理数 = 有理数, 只有都为$0$
即 $P_nk_{n-1}+Q_nk_{n-2}=h_{n-1}$ 且 $P_nh_{n-1}+h_{n-2}Q_n=k_{n-1}d$
所以有 $h_{n-1}^2-dk_{n-1}^2 = h_{n-1}(P_nk_{n-1}+Q_nk_{n-2})-k_{n-1}(P_nh_{n-1}+h_{n-2}Q_n)$
$= Q_n(h_{n-1}k_{n-2}-h_{n-2}k_{n-1})$
$= (-1)^nQ_n$
若$(x,y)$是 pell方程$x^2-dy^2=1$的解$(d>1,x>y>0)$,则
$|\sqrt{d} - \frac{x}{y}| = |\frac{dy^2-x^2}{y^2(\sqrt{d}+\frac{x}{y})}| < \frac{1}{2y^2}$ (从一定程度上说明了 为什么前面要去证明 小于$\frac{1}{2y^2}$)
根据前面的结论, 知道满足这个表达式的一定是 无理数$\sqrt{d}$ 的 渐进数, (但渐进数不一定是解)
(Yang.pdf那个paper下面的部分蛮多笔误的 不过能看懂证明思路)
因为上面有 $h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n$ 也就是如果要满足pell方程 那么$|Q_n|=1$,分类讨论$Q_n$
假设 $\sqrt{d}$的 最小周期长度为l
$Q_n \neq -1, n > 0$
证明
注意到上面根据$\sqrt{d}$的表达式 证明了$n>0$时,$x_n$是纯循环连分数,也就是reduced 二次无理数
如果$Q_n = -1$ 因为$x_n=\frac{P_n+\sqrt{d}}{Q_n}$,所以有 $x_n=-P_n-\sqrt{d} > 1$,有$-1<-P_n+\sqrt{d} < 0$ (Galois)
但$\sqrt{d} < P_n < -\sqrt{d} - 1$,矛盾 所以$Q_n \neq -1$, 对于$Q_0 = 1$也不为$-1$,得证
$Q_n = 1$当且仅当$n$为循环节长度的倍数才有
证明
若于$n>1$若$Q_n=1$那么有$x_n=P_n+\sqrt{d}$,它的共轭 $-1 < P_n-\sqrt{d} < 0$ 即 $P_n=\lfloor \sqrt{d} \rfloor$所以 $x_n = \lfloor \sqrt{d} \rfloor + \sqrt{d}$
$ \lfloor \sqrt{d} \rfloor +\sqrt{d} = x_n = 2\lfloor\sqrt{d}\rfloor + \frac{1}{\frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}} $ 即 $ x_{n+1} = \frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}$
$ \sqrt{d} = x_0 = \lfloor \sqrt{d} \rfloor + \frac{1}{\frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}}$ 即 $x_1 = \frac{1}{\sqrt{d} - \lfloor \sqrt{d} \rfloor}$
说明了 它的下一个数$x_{n+1} $和$x_1$相等, 这说明如果$Q_n = 1$ 那么n是当且仅当循环节长度的倍数(如果为1则循环节长度)
最后回到这里 $h_{n-1}^2-dk_{n-1}^2=(-1)^nQ_n = (-1)^n $ 也就是再看个奇偶,最后得到了pell方程和连分数比较紧密的结论
假设 $\sqrt{d}$的 最小周期长度为$l$
那么对应pell 方程的最小解
$(x,y) = {h_{l-1},k_{l-1}}$ 长度为偶数
$(x,y) = {h_{2l-1},k_{2l-1}}$ 长度为奇数
方法涉及
然后还有很多整数的离散性质
millersville periodic-continued-fractions
下面这个youtube非常推荐,他讲得很系统,并不是证明了就好,而是按照了每步都能抽象出结论的推导过程,然后和连分数相关的没讲,主要在讲pell 方程的解的性质
YouTube:Number Theory:Pell’s Equation part 1
A short proof and generalization of Lagrange’s theorem on continued fractions
purely periodic continued fractions
有些结论在证明过程中其实是缩小了范围,有些结论其实放大定义域之类也是成立的,但在证明过程中却只使用了所需要的部分。这类的从定义域和对应的要证明的逻辑不是“完美对应”的,但是足够,不知道是好还是不好。
证明的结论之间引用过程,感觉画成网状或者树状关系图会更好？
看youtube了上的讲解视频,会发现有一种写代码的抽取函数感觉,和我上面完全拆开证明不一样,抽函数的感觉其实在数学里大概是叫做“令”+“引理”,感觉和完全展开比较,的确能减少很多心智负担啊！如果你也能打开youtube建议去看看
另外比如有些 强结论要用的时候,即使你证出了相对弱的结论,但没有证明出强结论,其实相当于“没有用”,比如上面 基础解,的平方,的n次方,和任意另一组解能产生新的解的证明。当然如果能证明出,那些就是过程了,但不是步骤（虽然我上面有写进文中,因为要简洁整理的话,直接强结论证明,即可其它的弱的可以直接省略
虽然视频看的时候的确感觉到老师和同学的口算不如国内,但自从自己思考过十进制的意义以后,感觉数值计算都不再重要,有的是计算机,不需要人类来算。
youtuber james cook 有证明一个 同系数二元二次方程 之间的关系,可以用它来 从 不是解的东西里生成解(感觉好像不是特别行,因为一个等式的 四个值仅仅由两个变量控制而不是3个？)！(Quadradic Forms) Q(u+v)+Q(u-v)=2(Q(u)+Q(v)),然后以此建立树,考虑其中的“正负交替路线”river
多核没智力还是搞不动数学啊,
这篇文章整理了很多篇其它资料,所以在符号使用上还不够统一,之后看有空整理一下
在我快写完这一篇文章的时候发现了 一个超理论坛-连分数入门 注册需要一点点水平XD,这篇是带着例子讲解写的！(大自看了一下 感觉很棒 推荐), 又 有些性质证明方式不止一种,例如我本篇文章所抄来的证明 二次无理数和有循环节的充要 会感觉更漂亮一些
有些paper写到后面还是很多笔误,不过看通了也是能理解具体过程
有一个想法是 哪些结论是关键或者说证明的难点,其实可以这样想,现在,把文章中一些部分换成填空,你还能不能补全整个文章,不需要完全一样,只要能证明就行。这样想的话,就会知道所谓的难点是在哪。