灵光一现,代码实现

admin管理员组

文章数量:1516870

灵光一现,代码实现

题目 

用高精度计算出S=1！+2！+3！+…+n！（n≤10000）

其中“！”表示阶乘，例如：5！=5*4*3*2*1。

开始yy

看到题目是否一下子想到直接写两个高精模拟一遍，太naive了

用jiao想一想都知道时间肯定过不去的啊

这时候就要走一些旁门左道了

观察式子，1!+2!+3!+4!……n!，n!=(n-1)!*n

然后把式子从左到右会发现可以Sn=((( n+1)*(n-1))*(n-2))*……*1

可以用for(i:n-1) ans=(ans+1)*i表示

现在再看耗时的差别，加法由高精加变为整数加法明显简单了不少

乘法由高精乘高精变为高精乘整数，循环次数也少了

#include<cstdio>
using namespace std;
const int mod=1e8;
int n,base=4,l=1;
long long ans[10];
void mult(){for(int i=0;i<l;i++)ans[i]*=n;for(int i=0;i<l;i++){ans[i+1]+=ans[i]/mod;ans[i]=ans[i]%mod;}if(ans[l]) ++l;
}
int main(){scanf("%d",&n);ans[0]=0;while(n){++ans[0];mult();--n;}printf("%lld",ans[--l]);while(l--) printf("%08lld",ans[l]);return 0;
}

 这个膜1e8属于进制优化，简单的解释为数组的每一个单元存一个长度为8的子串

例如123456789在数组中的情况为a[0]=2345678,a[1]=1

转载于:.html

本文标签： 灵光一现代码实现