题解 P1727 【计算π】

kcm1996 · 2013-11-26 12:59:14 · 题解

因为观察了提交界面发现一群人毫无节操地交打表，而本弱菜多次TLE而引发的各种提交错误后痛定思痛决定福利大众，为后死者展望明丽的未来而决定写篇题解。。。。

众所皆知，求圆周率的公式有很多种，这些都可以在百度百科查到。。。

然而想要求出10000位小数这样的算法，首先要保证公式能在较小的时间内算出较多的精度位数。所以选取的公式即为:

pi/2=1+(1/3)+(1/3)*(2/5)+(1/3)*(2/5)*(3/7)……

显而易见用高精度记录分子乘积，在每个阶段都要除以当前阶段的分母来累计分母的乘积，然后每次都累计和一遍。

一开始数组只存一位然后TLE了，换成存两位就没问题啦。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>

using namespace std;

int n, len, side, Tot, hj, i, t1, t2, a[5105], A[5105];

int main() {
    freopen("1727.in", "r", stdin);
    freopen("1727.out", "w", stdout);
    scanf("%d", &n); len = (n + 20) / 2; a[1] = 2; 
    side = 1; Tot = 0; hj = 3; printf("3.\n");
    while (side && ++Tot <= 200000000) {
        for (t1 = t2 = 0, i = len - 1; i; i--)
            t1 = a[i] * Tot + t2, a[i] = t1 % 100, t2 = t1 / 100;
        for (t2 = 0, i = 0; i < len; i++)
            t1 = a[i] + t2 * 100, a[i] = t1 / hj, t2 = t1 % hj; side = 0;
        for (i = len - 1; i; i--) {
            A[i - 1] += (A[i] + a[i]) / 100; 
            A[i] = (A[i] + a[i]) % 100;
            side |= (a[i] / 10);
            side |= (a[i] % 10); hj += 2;
        }
    } hj = 0;
    for (i = 2; i <= n + 1; i++) {
        hj += 2; if (hj > n) {
            printf("%d", A[i] / 10);
            break;
        }
        if (A[i] < 10) printf("0"); printf("%d", A[i]);
        if (i != n + 1) {
            if ((i - 2 + 1) % 25 == 0) printf("\n");
            else if ((i - 2 + 1) % 5 == 0) printf(" ");
        } if (hj == n) break;
    }
    return 0;
}