洛谷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 方法
参考文献：
