YZOJ P2697 画圆

时间限制：1000MS      内存限制：131072KB

难度： \(5.1\)

• 题目描述

在初中数学课上，\(Alkri\) 学习了圆的相关知识，他对与圆有关的问题更加感兴趣了。

\(Alkri\) 想在平面直角坐标系的第一象限中依次画 \(n\) 个与两坐标轴均相切的圆，其中，第 \(1\) 个圆的半径为 \(r\)，之后的每个圆都比上一个圆大，且与上一个圆相切，也就是说，对所有整数 \(2 \leq i \leq n\)，第 \(i\) 个圆的半径大于第 \(i-1\) 个圆的半径且与第 \(i-1\)个圆相切。

例如当 \(n=3\) 时，三个圆 \(C_1, C_2, C_3\) 如下图所示（由于 \(C_3\) 比较大，未画完整）：

现在，\(Alkri\) 很好奇：第 \(n\) 个圆的半径 \(R\) 到底有多大？他知道 \(R\) 不一定是整数（真聪明！），并且可能非常大，所以只需要你保留 \(R\) 的整数部分（向下取整）的末尾 \(p\) 位数字即可。

• 输入格式

输入仅一行，包含三个整数 \(n\)，\(r\)，\(p\)，意义如题目所述。

• 输出格式

输出仅一行一个整数，表示第 \(n\) 个圆的半径 \(R\) 的整数部分的末尾 \(p\) 位。注意当 \(R\) 的整数部分实际位数超过 \(p\) 时需要输满 \(p\) 位（即需要保留前导0），如果实际位数不满 \(p\) 位则不用补前导 0 。

• 输入样例

• 输出样例

• 样例说明

第 \(10\) 个圆的半径整数部分为 \(38808989\)，要求输出整数部分的末尾 \(5\) 位数，因此输出 \(08989\) 。注意保留前导 0 。

• 数据规模与约定

 

 

 

---

 

 

 

通过简单的数学计算可得下一个圆的半径是前一个圆的半径的 \(3+2\sqrt2\) 倍。（不要问为什么，题解说的

那么答案就是 \((3+2\sqrt2)^{n-1}r\) ，首先 \(50pts\) 就到手了。因为 \(n\) 很大的时候肯定会爆精度，所以无法开什么 long double  暴算。

高精度是肯定要写的，那么怎么写就是一个比较关键的问题。

可以新定义一个结构体表示 \(a+b\sqrt2\) ，其中 \(a, b\) 是两个高精度整数。这样就可以用整数表示出带根号的数了！这样，\((a+b\sqrt2)(c+d\sqrt2)=(ac+2bd)+(ad+bc)\sqrt2\) ，就是两个结构体相乘的方法了。

所以答案就是 \((3+2\sqrt2)^{n-1}r=Ar+B\sqrt2r=\cdots\cdots\) 。。。。。。好像没什么用？好像还是需要 \(\sqrt2\) 的近似值才能算？？？

这个时候就要想起奥数班sxb老师的教诲（好像当时数字也是这个来着的）

发现这个 \(\sqrt2\) 是真的很讨厌，就必须想办法把它弄掉。

注意到二项式定理。

\((a+b)^{n}=\sum\limits_{i=0}^{n} C_n^i a^{n-i} b^i\)

\((a-b)^{n}=\sum\limits_{i=0}^{n} \left([i\;\bmod\; 2\; =\; 0](C_n^i a^{n-i}b^i)+[i\; \bmod\; 2 \;=\; 1](-C_n^i a^{n-i}b^i)\right)\)

写成这样其实就非常清楚了，所以把它们相加的话

\((a+b)^n+(a-b)^n = 2\sum_{i=0}^{n} ([i\;\bmod\; 2\; =\; 0])(C_n^i a^{n-i}b^i)\)

在这里，若使 \((3+2\sqrt2)^{n-1}=A+B\sqrt2\) ，那么 \((3+2\sqrt2)^{n-1}+(3-2\sqrt2)^{n-1}=2A\) 。

所以答案就是 \((3+2\sqrt2)^{n-1}r=2Ar-(3-2\sqrt2)^{n-1}r=\cdots\cdots\) 。。。。。。好像没什么用？不！！有非常大的用处！！！！！！

因为 \(3-2\sqrt2 \approx 0.17 < 1\) ，所以可以试着计算一下 \((3-2\sqrt2)^{14} \approx 2 \times 10^{-11} < 10^{-10} < \frac{1}{r}\) ，也就意味着 \(n\) 足够大（其实也就 \(15\)）时，\((3-2\sqrt2)^{n-1}r < 1\) ，所以答案就是 \(2Ar-1\) 。

这样 \(n\) 小的时候 long double  暴算一下，\(n\) 大的时候高精算一下就可以通过本题了！！！

（还要注意的是，保留小数位数那里前导 0 的判断要十分谨慎，我调了2d才调出来w