2172. 神秘的常数π-改正版

【题目描述】

【题目1402原题】

   古希腊的大哲学家毕达哥拉斯(Pythagoras)很早就注意到数学与大千世界的联系，对数学科学的发展有着功不可没的贡献。他还创立了古希腊影响最深远的学派之一—毕达哥拉斯学派。毕达哥拉斯学派对数字的认识达到了审美的高度。他们相信，在这个世界中"万物皆数"，所有事物都可以用整数和整数之比来描述。

   然而，毕达哥拉斯学派有一位叫做希帕索斯(Hippasus)的学者发现，边长为1的正方形的对角线长度不能用整数比来表示。这一惊人的发现使他被扔进的大海。

   为了探索这些奇妙的数字。CH同学需要一个计算精度极高的程序来计算无理数的近似值。

   CH同学决定从他接触的第一个无理数开始研究—π。

计算π的方法多种多样，CH同学为你提供了一些参考方案：

【原题End】

那个...原题测试数据有误，笔者特将其改正，完善后重新上传（笔者并非原题笔者）。

（OIers：好人啊！原题实在过不去啊！）

打表者勿入，最小N为131072。但各种限制更加宽松。

（OIers：打表传不上去啊怪不得...）

然而这意味着……

（OIers：又要写高精度！）

另：增加前两个测试点作为骗分测试点，打表者随意~~~

改正版题目描述与原题一致。

另添加几个较为有用的公式：

1.简洁神器——BBP公式（贝利－波尔温－普劳夫公式）：

（注意：没有高精度分母）

2.高速神器——GLA公式（高斯-勒让德公式）：

初始化：

迭代：

最终计算：

3.神器中的神器——FFT（快速傅里叶变换，用于高精度乘法）：

(略)

有了上面的神（ti）器（shi），相信各位OIers定能AC此题！

警告：本题I/O量极大，不宜使用C++流I/O！

改正版测试数据来源：Wolfram Mathematica 9

【输入格式】

一个整数N（描述精度），表示小数点后的位数

与原题不同的是，N≤17000000。

【输出格式】

π的近似值,为了方便观察， 第一行为“PI=3.”

(第二行无数据，以便观察)

第三行起为小数部分。为便于观察，每10个数字为一组（组与组之间空一格），每5组为一行，每20行间空一行。

【样例输入】

15

【样例输出】

Pi=3.

1415926535 89793

【提示】

尽量保证精度。若精度为n，则小数点后第n+1位不予考虑，直接舍弃，不进行四舍五入运算。

数据规模：N≤17000000

【来源】

undefined