洛谷P1727 计算π 题解

题目链接：P1727 计算π

题意：

计算 $\pi$ 的小数点后 $n(n \le 10000)$​ 位。

输入格式：

一行，$n$

输出格式：

先输出一行 3. ，然后$10$ 个数一空格，$50$​ 个数一换行。

学 OI 这么久，我居然不会计算圆周率。

首先有梅钦公式

$$\frac{\pi}{4}=4 \arctan \frac{1}{5}-\arctan \frac{1}{239}$$

接着有麦克劳林级数

$$\begin{aligned} \arctan (x)&=\sum_{n=0}^{\infty} \frac{(-1)^n}{2 n+1} x^{2 n+1} \\[6pt] &= x-\frac{x^3}{3}+\frac{x^5}{5}-\cdots &(\forall x:|x| \leq 1, x \neq \pm i) \end{aligned}$$

然后用 Python 打个表，C++ 输出即可。

时间复杂度 $\mathcal{O}(n^2)$

Python 代码：

n = int(input())
_1 = 10 ** (n + 10)
a = _1 * 4 // 5
b = _1 // -239
sum = a + b
for i in range(3, n * 2, 2):
    a //= -25
    b //= -57121
    sum += (a + b) // i
pi = sum * 4
pi = pi // 10 ** 10 - 3 * 10 ** n
# print("3.%s" % (pi))
print("3%s" % (pi), file = open('check.out', 'w'))

C++ 代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)())
#define S(x) #x

char s[] = S(3141592...); // 这个表太长了我不贴全了
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; cout << "3.\n";
    for(int i = 1; i <= n; i++) {
        cout << s[i];
        if(i % 10 == 0) cout << " \n"[i % 50 == 0];
    }
    return 0;
}

---

不过听说直接用梅钦公式收敛速度可能慢一些

那就顺便科普一下梅钦类公式吧，听说收敛更快，但复杂度其实没变。

梅钦类公式（Machin-like formula）

$$c_0 \frac{\pi}{4}=\sum_{n=1}^N c_n \arctan \frac{a_n}{b_n}$$

其中 $a_n,b_n$ 为正整数且 $a_n < b_n$ ，$c_n$ 为非零整数，且 $c_0$ 为正整数。

什么？你问我 $a,b,c$​ 是啥？其实“随便”啥都可以哦 qwq

具体地，根据角的和差公式

$$\begin{aligned} & \sin (\alpha+\beta)=\sin \alpha \cos \beta+\cos \alpha \sin \beta \\ & \cos (\alpha+\beta)=\cos \alpha \cos \beta-\sin \alpha \sin \beta \end{aligned}$$

若 $\displaystyle -\frac{\pi}{2}<\arctan \frac{a_1}{b_1}+\arctan \frac{a_2}{b_2}<\frac{\pi}{2}$​ ，则有

$$\arctan \frac{a_1}{b_1}+\arctan \frac{a_2}{b_2}=\arctan \frac{a_1 b_2+a_2 b_1}{b_1 b_2-a_1 a_2}$$

反复应用这个方程，就可以得到所有的梅钦类公式啦~

比如最原始的梅钦公式可以这么推导

$$\begin{aligned} & 2 \arctan \frac{1}{5} \\ & =\arctan \frac{1}{5}+\arctan \frac{1}{5} \\ & =\arctan \frac{1 \times 5+1 \times 5}{5 \times 5-1 \times 1} \\ & =\arctan \frac{10}{24} \\ & =\arctan \frac{5}{12} \\ & 4 \arctan \frac{1}{5} \\ & =2 \arctan \frac{1}{5}+2 \arctan \frac{1}{5} \\ & =\arctan \frac{5}{12}+\arctan \frac{5}{12} \\ & =\arctan \frac{5 \times 12+5 \times 12}{12 \times 12-5 \times 5} \\ & =\arctan \frac{120}{119} \\ & 4 \arctan \frac{1}{5}-\frac{\pi}{4} \\ & =4 \arctan \frac{1}{5}-\arctan \frac{1}{1} \\ & =4 \arctan \frac{1}{5}+\arctan \frac{-1}{1} \\ & =\arctan \frac{120}{119}+\arctan \frac{-1}{1} \\ & =\arctan \frac{120 \times 1+(-1) \times 119}{119 \times 1-120 \times(-1)} \\ & =\arctan \frac{1}{239} \\ & \frac{\pi}{4}=4 \arctan \frac{1}{5}-\arctan \frac{1}{239} \\ & \end{aligned}$$

那就给一个网上找的公式吧

$$\frac{\pi}{4} = 44\arctan\frac{1}{57} + 7\arctan\frac{1}{239}-12\arctan\frac{1}{682}+24\arctan \frac{1}{1294}$$

如果你觉得 $\mathcal{O}(n^2)$ 太慢，可以看看参考文献1，里面有讲 $\mathcal{O}(n\log^2 n)$ 的方法

据《理性愉悦——高精度数值计算》说是目前计算初等函数时间复杂度最低的方法：AGM 方法

---

参考文献：

[1] https://www.luogu.com.cn/article/42mm7y25

[2] 梅钦类公式 - 维基百科，自由的百科全书