题目链接： HDU 7217
题意：
题目给你可以计算 (π) 的公式：
(pi = sum_{k=0}^{infty}[frac{1}{16^k}(frac{4}{8k+1})-(frac{2}{8k+4})-(frac{1}{8k+5})-(frac{1}{8k+6})])
告诉你可以求十六进制下的小数点后 (π) 的第 (n) 位，而不用计算前 (n-1) 项。
十六进制表示下，问你 (π) 的小数点后的第 (n) 位是多少 $ (1 ≤ n ≤ 100000)$ 。
Paper链接：
BBP Paper http://www.experimentalmath.info/bbp-codes/bbp-alg.pdf
简要题解：
其实看上面的 (Paper) 就知道怎么做了。
我简单解析一下。
把公式的第一项拿出来分析：
(sum_{k=0}^{infty}frac{1}{16^k}(frac{4}{8k+1}) = sum_{k=0}^{infty}(frac{4}{16^k(8k+1)}) = sum_{k=0}^{infty}(frac{1}{16^k(8k+1)})).
把公式拆分：
(sum_{k=0}^{infty}(frac{1}{16^k(8k+1)}) = sum_{k=0}^{infty}(frac{1}{16^k(8k+1)}) = sum_{k=0}^{n}(frac{1}{16^k(8k+1)}) + sum_{k=n + 1}^{infty}(frac{1}{16^k(8k+1)})).
拆分之后我们就可以得到第 (n) 位。
将式子乘上 (16^n) ,使得小数点往后移动 (n) 位。
([sum_{k=0}^{n}(frac{1}{16^k(8k+1)}) + sum_{k=n + 1}^{infty}(frac{1}{16^k(8k+1)})]*16^{n}==> sum_{k=0}^{n}(frac{16^{n-k}}{(8k+1)}) + sum_{k=n + 1}^{infty}(frac{16^{n-k}}{(8k+1)})).
前一项 (sum_{k=0}^{n}(frac{16^{n-k}}{(8k+1)})) 为了避免高精度，可以化成 (sum_{k=0}^{n}(frac{16^{n-k} mod (8k+1)}{(8k+1)})).
后一项 (sum_{k=n + 1}^{infty}(frac{16^{n-k}}{(8k+1)})) 就不用简化了,将 (infty) 取够一定范围就可以了。
令 (S_1 = sum_{k=0}^{n}(frac{16^{n-k}}{(8k+1)}) + sum_{k=n + 1}^{infty}(frac{16^{n-k}}{(8k+1)})).
那么，答案就是 (4S_1 - 2S_2 - S_3 - S_4)的小数部分。因为得到的只是小数部分，所以再乘以 (16) 后，得到的整数部分转化成十六进制就可以啦。
时间复杂度：(O(nlogn))
所以，我是不是可以出一道关于计算二进制表示下的 (log2) 的题 ???
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char print(int x)
{
if(x>=0 && x<=9)return x + '0';
return x+55;
}
ll qpower(ll a, ll b, ll mod)
{
ll res = 1;
while(b)
{
if(b & 1) res = a * res % mod;
b >>= 1;
a = a * a % mod;
}
return res;
}
double bbp(int n,ll k,ll b)
{
double res = 0;
for(int i=0;i<=n;i++)
{
res += (qpower(16,n-i,8*i+b) * 1.0/(8*i+b));
}
for(int i = n + 1;i <= n + 1000 + 1;i++)
{
res += (powf(16,n-i)* 1.0/(8*i+b));
}
return k * res;
}
int main()
{
int t,n;
cin>>t;
int cas = 1;
while(t--)
{
double ans = 0;
cin>>n;
n--;
ans = bbp(n,4,1) - bbp(n,2,4) - bbp(n,1,5) - bbp(n,1,6);
// cout<<"ans="<<ans<<endl;
ans = ans - (int)ans;
if(ans<0)ans+=1;
ans*=16;
char c ;
c = print(ans);
printf("Case #%d: %d %c
",cas++,n+1,c);
}
return 0;
}