hdu 6217 A BBP Formula 公式题

题意

已知公式：$\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 = ;

    while(b)

    {

        if(b&)  ret = ret * a % mod;

        a = a * a % mod;

        b >>= ;

    }

    return ret;

}

double  BBP(int c1, int c2, int  n)

{

    double ret = 0.0;

    for(int i = ;i <= n;i++)  ret += qpow(, n-i, *i+c2)*1.0/(*i+c2);

    return c1*ret;

}

int main()

{

    int T, kase = ;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &n);

        double res = BBP(, , n-) - BBP(, , n-) - BBP(, , n-) - BBP(, , n-);

        res = res - (int)res;

        if(res < )  res = res + ;

        printf("Case #%d: %d ", ++kase, n);

        int ans = (int)(res*);

        if(ans < )  printf("%d\n", ans);

        else  printf("%c\n", 'A'+ans-);

    }

    return ;

}

参考链接：https://www.cnblogs.com/LzyRapx/p/7802790.html

巴特西

hdu 6217 A BBP Formula 公式题

题意

分析

最新文章

热门文章