连分数 - 洛谷保存站

# 连分数

## 简介

连分数是形如以下图片的数

![](https://img1.baidu.com/it/u=3829970774,426188817&fm=26&fmt=auto)

其中 $a_0$ 是一个整数，且 $a_1,a_2,...,a_n$ 都是正整数。如果 $a_0,a_1,...,a_n$ 都是整数且其是有限的，则我们称这个分数为有限简单连分数，记作 $[a_0;a_1,...,a_n]$。而且因为 $a_0$ 是这个数本身的整数部分，对于连分数部分没有影响，所以要用“；”来表示。

连分数可以有效并精确的表示所有的有理数，并且是有限的。从而避免了无限循环小数这种麻烦的实数表示方式。

比如 $\LARGE\frac{415}{93}$，它约为 $4.4624$，但是用连分数来表示就是 $\Huge4+\frac{1}{2+\frac{1}{6+\frac{1}{7}}}$，我们可以用 $[4;2,6,7]$ 来表示这个数。

## 性质

- 一个数的连分数的表示是有限的，当且仅当这个数是有理数。

- 任何有理数的连分数的表示是唯一的，当且仅当它没有尾随的 $1$，就是指 $[a_0;a_1,...,a_n,1]=[a_0;a_1,...,a_n+1]$ 这种特殊的情况要除掉。

- 无理数的连分数的表示是唯一的。

- 连分数的项将会循环，当且仅当这个数是一个二次无理数的连分数表示。二次无理数就是整数系数的二次方程的实数解。即 $a+b\sqrt c$，$(a,b,c\in Q)$。

- 连分数表示的任意前一部分可以比传统表示实数的方法更加逼近这个数。如 $\pi$ 有 $\frac{314}{100}$ 和 $\frac{31415}{10000}$ 这两种逼近方法，但是这没有 $[3;7,15,1,292]$ 这种误差更小，甚至小了上 $10$ 倍。这用于无理数的逼近有着极为 $nice$ 的效果。

下面是连分数理论中地位极高的两个数列：

对于连分数 $C=[a_0,a_1,...,a_n]$，我们称 $C_k=[a_0,a_1,...,a_k]$ 是 $C$ 的第 $k$ 个渐进分数，特别地 $C_0=a_0$。

我们定义一对数列 $[p_k],[q_k](k=0,1,2,......,n)$ 如下：

$p_0=a_0$

$p_1=a_1\times p_0+1$

$p_k=a_k\times p_{k-1}+p_{k-2}$

$q_0=1$

$q_1=a_1$

$q_k=a_k\times q_{k-1}+q_{k-2}$

$C_k$ 与 $p_k,q_k$ 有如下关系：

- $k∈[0,n]$ 时，$C_k=\frac{p_k}{q_k}$

- $k∈[1,n]$ 时，都有 $p_k\times q_{k-1}-q_k\times p_{k-1}=(-1)^{k-1}$

$k∈[2,n]$ 时，都有 $p_k\times q_{k-2}-q_k\times p_{k-2}=(-1)^{k}\times a_k$

- $(p_k,q_k)=1(k∈[1,n])$

我们称 $s_k=[a_1,a_2,...,a_k]$（$0\le k\le n$）为这个连分数的循环节。

- 且，我们有 $a_k=a\cdot a_0$。

## 求二次无理数的循环节

有了循环节，我们可以只用简短的一部分来描述所有的二次无理数。

接下来我来介绍一种用实数方法来求二次无理数的连分数的方法。

如：我们要求 $\sqrt{2}$ 的连分数。

$\sqrt{2}\approx1.414213$

我们首先取其整数部分，即 $a[0]=1$。

然后将其小数部分取倒数，即 $\frac{1}{0.414213}\approx2.414216$。

我们再取其整数部分，即 $a[1]=2$。

接着我们再将其小数部分取倒数，即 $\frac{1}{0.414216}\approx2.414199$。

如果我们保留的小数足够大，那么我们得到的倒数结果将一直是一个值。

由于我们是用小数计算，所以会有精度误差，然而如果我们原模原样的去算，会发现它的每一项都是循环的。

比如 $\sqrt{2}$ 的循环节是 $[2]$。

- 定理：$a_k=2\cdot a_0$（$k$ 是循环节的最后一位）。

代码实现：

```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxN=1e5+5;
int n,a[MaxN],cnt;
int main(){
	scanf("%d",&n);
	double g=sqrt(n);
	a[0]=g;
	g-=a[0];
	while(a[cnt]!=a[0]*2){
		if(g>=1){
			a[++cnt]=g;
			g-=a[cnt];
		}
		g=1/g;
	}
	for(register int i=0;i<=cnt;i++){
		printf("%d ",a[i]);
	}
	return 0;
}
```

然后我们发现，我们可以不用实数范围来计算一个二次无理数，反而，我们可以通过整数来求解。

由于我们每次在分母有理化的时候，都会出现形如 $\frac{a+\sqrt{n}}{b}$的分数，如 $\sqrt{7}$ 展开式中会出现 $\frac{2+\sqrt{7}}{3}$，$\frac{1+\sqrt{7}}{2}$等。

如果我们给分子加减一个 $\le k_{n-1}$ 的最大整数 $k_n$，使 $b|(a+k_{n-1})$，那么我们就可以得到这一步所要得到的连分数的值。接着我们继续重复这个操作，然后利用定理来结束后面不必要的计算。且我们记过渡数为：$c_n=n-k_n^2$。

例如：

$\sqrt{n}=k_0+\sqrt{n}-k_0$

$=k_0+\frac{1}{\sqrt{n}-k_0}$（第一次操作得到的值是 $k_0$，后面得到的值我们直接用 $a$ 来表示）。

我们得到了 $a_0=k_0$。接着：

$=a_0+\frac{\sqrt{n}+k_0}{c_0}=a_0+\frac{k_0+k_1+\sqrt{n}-k_1}{c_0}=a_0+a_1+\frac{c_0}{\sqrt{n}-k_1}$（$a_1=\frac{k_0+k_1}{c_0}$）

$=a_0+a_1+\frac{\sqrt{n}+k_1}{c_1\div c_0}=a_0+a_1+\frac{k_1+k_2+\sqrt{n}-k_2}{c_1\div c_0}=a_0+a_1+a_2+\frac{c_1\div c_0}{\sqrt{n}-k_2}$（$a_2=\frac{k_1+k_2}{c_1\div c_0}$）

……

代码

```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxK=5e3;
int n,a[MaxK],c[MaxK],k[MaxK],cnt,sk;
int main(){
	scanf("%d",&n);
	sk=sqrt(n);
	a[0]=sk;
	c[0]=1;
	k[0]=0;
	while(a[cnt]!=sk*2){
		k[cnt+1]=a[cnt]*c[cnt]-k[cnt];
		c[cnt+1]=(n-k[cnt+1]*k[cnt+1])/c[cnt];
		a[cnt+1]=(sk+k[cnt+1])/c[cnt+1];
		cnt++;
	}
	for(register int i=0;i<=cnt;i++){
		printf("%d ",a[i]);
	}
	return 0;
}
```
于是无限连分数就这样解决了！

正在渲染内容...