1.最近看到有学弟在说BBP算法，然后就写一下这个东东。
2.BBP其实是三个人，然后这个算法是干嘛的嘞，其实是快速的求某些无理数的第n为数字或者第n位以后的一串数字。比如求PI，log2,log3等等。下面来说明一下它是怎么求PI的在16进制下的第n位数字的。（什么，为什么是16进制？，看完就明白了）
3.首先给出一个PI的级数求和公式：
（这玩意怎么来的？emmmm，泰勒展一下就出来了吧，虽然我没展）。
看一下HDU 6217，题意十分的直白，求PI的第n位数字。
我们知道，比如给你一个小数：1.23456789.现在求这个数的第4位小数，咋整？其实很简单，你把小数点放在4和5之间，然后类型强制转换一下，把整数去掉，再乘个10就是第4位小数。一般化一下，对于第n位小数，先把小数点移动到它的前边，然后整数部分去掉，再乘个基底就是答案。这也就是BBP算法的核心了。那么对于PI，我们首先把这个和式拆一下，拆成四个求和，然后对于每一个求和，考虑：
首先时两边同时乘16^d,这样在16进制下，小数点就会后移动d-1位。然后将整个求和式子分为两部分，前边的部分就是d>k,后边时d<k.当d<k时，这就是一个小数，对答案有贡献，然后分子对分母取模，这也是直接计算小数部分，把整数部分全部去掉。这样全部加起来就是小数部分，然后再*16，就是16进制下的答案。到这里也解释了为啥只能求16进制下的数位。同理，如果求log2这个数的第n位，由于使用泰勒展开之后是2^k,所以只能求二进制下的数位。emmm，基本上就是这些了。
最后附上HDU 6217的代码:
#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define ll long long
ll qpow(ll a, ll b, ll mod)
{
ll res = 1;
while (b)
{
if (b & 1)res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
double BBP(int n, double a, double b)
{
double r = 0;
for (int k = 0; k <= n; k++) r += qpow(16, n - k, 8 * k + b) * 1.0 / (k * 8.0 + b);
return r * a;
}
double BBPformular(int n)
{
return BBP(n, 4, 1) + BBP(n, -2, 4) + BBP(n, -1, 5) + BBP(n, -1, 6);
}
int main() {
int t;
scanf("%d", &t);
for (int c = 1; c <= t; c++) {
int n;
scanf("%d", &n);
n--;
double r = BBPformular(n);
r = r - (ll)r;
if (r < 0)r += 1.0;
r *= 16;
int res = r;
printf("Case #%d: %d %c\n", c, n + 1, res > 9 ? res - 10 + 'A' : res + '0');
}
return 0;
}