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