题解 P1727 【计算π】

正如楼上大佬所说，确实有很多人无节操的打表，但是本蒟蒻**懒得打表**，于是便决定写一篇题解来介绍一下这道题的**正解**~~（这怕是这道题最短的代码了）~~ ## 算法 和楼上大佬一样，我也采用了如下公式： $$\frac{\pi}{2}=1+\frac{1!}{3!!}+\frac{2!}{5!!}+\frac{3!}{7!!}+...+\frac{k!}{(2k+1)!!}+...$$ 其中，$n!=1\times 2\times 3\times ...\times n$，$n!!=1\times 3\times 5\times ...\times n(n\text{为奇数})$ 然后我们对公式进行展开和调整： π/2 = 1 + 1!/3!! + 2!/5!! + 3!/7!! + ... + k!/(2×k+1)!! = 1 + 1/3 + (1×2)/(3×5) + (1×2×3)/(3×5×7) + ... + (1×2×...×k)/(3×5×...×(2k+1)) = 1 + 1/3 + (1/3)×(2/5) + (1/3)×(2/5)×(3/7) + ... + (1/3)×(2/5)×...×(k/(2k+1)) = (1/3)×(2/5)×...×(k/(2k+1)) + ... + (1/3)×(2/5)×(3/7) + (1/3)×(2/5) + 1/3 + 1 = (k/(2k+1))×...×(2/5)×(1/3) + ... + (3/7)×(2/5)×(1/3) + (2/5)×(1/3) + 1/3 + 1 = (((((k/(2k+1)+1)×((k-1)/(2(k-1)+1)+1)×...)×3/7+1)×2/5+1)×1/3+1)/1 = (((((1/(2k+1)×k+1)/(2(k-1)+1)×(k-1)+1)/...)/7×3+1)/5×2+1)/3×1+1)/1 然后我们就可以发现，只需要循环做除法、乘法、加1，直到除数为1为止 但是我们发现一个问题，题目要求求到$\pi$的**10000位**，所以我们只能用**大整数除法**来解决 所以代码如下 ## 代码 ```cpp #include <cstdio> using namespace std; int a=10000,b,c=70000,d,e,f[70001],g,n=-1,len; char str[100005]="141"; int main() { scanf("%d",&len); for(;b-c;) f[b++]=a/5; for(;d=0,(g=c*2)&&n<=len;c-=14,~n&&sprintf(str+n, "%.4d",e+d/a),n+=4,e=d%a) for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b); printf("3."); for(register int i=0;i<len;i++) { if (!(i%10)) printf(" "); if (!(i%50)) printf("\n"); printf("%c", str[i]); } return 0; } ``` 算上空行**不到20行**，这真的是这道题最♂短♂的代码了orz！