已知公式：$\pi=\sum_{k=0}^{\infty}\left[\frac{1}{16^{k}}\left(\frac{4}{8 k+1}-\frac{2}{8 k+4}-\frac{1}{8 k+5}-\frac{1}{8 k+6}\right)\right]$
求 $\pi$ 的第 $n$ 项。
WIKI上有：π的BBP位抽取算法
这类公式是用来求解一些无理数常数的公式,特点是不需要求解前n-1位也能去算第n位
将公式乘以 $16^n$ 就能将小数点移动到第 $n$ 位。
我们只需要将小数点移动到第 $n-1$ 位，减去整数部分，将小数部分乘 16 就是16进制下的第 $n$ 位。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int n; ll qpow(ll a, ll b, ll mod) { ll ret = 1; while(b) { if(b&1) ret = ret * a % mod; a = a * a % mod; b >>= 1; } return ret; } double BBP(int c1, int c2, int n) { double ret = 0.0; for(int i = 0;i <= n;i++) ret += qpow(16, n-i, 8*i+c2)*1.0/(8*i+c2); return c1*ret; } int main() { int T, kase = 0; scanf("%d", &T); while(T--) { scanf("%d", &n); double res = BBP(4, 1, n-1) - BBP(2, 4, n-1) - BBP(1, 5, n-1) - BBP(1, 6, n-1); res = res - (int)res; if(res < 0) res = res + 1; printf("Case #%d: %d ", ++kase, n); int ans = (int)(res*16); if(ans < 10) printf("%d\n", ans); else printf("%c\n", ‘A‘+ans-10); } return 0; }
参考链接：https://www.cnblogs.com/LzyRapx/p/7802790.html
原文：https://www.cnblogs.com/lfri/p/11705042.html