阶乘计算之大数阶乘与快速取模阶乘计算

2019-04-13 15:29发布

站内文章 / 模拟电子
17804 0 1186
class="markdown_views prism-github-gist">

大数阶乘的常规运算

即数学的模拟运算。一位一位的乘，有进位就进位。 #include #define _xx ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; typedef long long LL; //1,2,6,24,120,720,5040,40320,362880,3628800, int a[40000]; int main() { int n; while(cin>>n){ memset(a,0,sizeof(a)); a[1]=1; int i,j,len=1,rest; for(i=2;i<=n;i++){ rest=0; for(j=1;j<=len;j++){ a[j]=a[j]*i+rest; rest=a[j]/10; a[j]=a[j]%10; } while(rest){ a[j++]=rest%10; rest/=10; } len=j-1; } for(i=len;i>=1;i--) cout<cout<

引例之速求阶乘末尾0的个数

我们知道末尾0至于阶乘中的因子2*5有关，并且阶乘n中5的数量比2的数量少很多。
如果我们要考虑阶乘尾数0的个数，就只要知道有多少个2*5即可，只要知道5的个数即可。
所以我们只要算出N！中5的个数。
而N！中5的个数公式=n/5+n/25+n/125…n/(5^m)
举个例子。n=1000。
1-1000中5有a1=200。
1-1000有25有a2=40。
1-1000有125有a3=8。
1-1000有625有a4=1。
所以5的个数有5+25+125+625。为什么直接加？因为如1-1000中的数75，它有2个5。他在a1中算过一次，在a2中也算过一次。
so。实现代码如下。 #include using namespace std; //n![1~10]：1,2,6,24,120,720,5040,40320,362880,3628800, int main() { int n; cin>>n; int ans=0; while(n){ ans+=n/5; n/=5; } cout<return 0; }

大数阶乘要取模，快速取模

试用情况：当数很大，普通的阶乘取模很慢，需要用快速阶乘取模的算法。
具体算法是这样。
由10！
=1*2*3*4*5*6*7*8*9*10
=1*2*3*(2*2)5(2*3)7(2*2*2)(3*3)(2*5)
=1*(2^8)(3^4)(5^2)*7
我们可以想到，如果把每个数的质因数都分解出来，并且统计每种质因子有多少个，我们就可以多次使用二分求幂，再把它们的结果乘起来。注意这里并不是真的要老老实实地去分解每个数的质因子。对于每个质数x，我们可以很快算出前n个正整数一共包含有多少个质因子x（参考求n!末尾有多少个0么）。 #include #define _xx ios_base::sync_with_stdio(0);cin.tie(0); using namespace std; typedef long long LL; //n![1~10]：1,2,6,24,120,720,5040,40320,362880,3628800, const int mod=1000000007; int prime[2000]; bool vis[10005]; int cnt=0; void init() { int m=sqrt(10005); for(int i=2;i<=m;i++) { if(!vis[i]){ for(int j=i*2;j<=10005;j+=i){ vis[j]=true; } } } for(int i=2;i<=10000;i++) if(!vis[i])prime[cnt++]=i; } LL poww(LL a,LL b,LL m) { LL ans=1; while(b) { if(b&1) ans=ans*a%m; a=a*a%m; b>>=1; } return ans; } int main() { _xx; init(); int n; while(cin>>n){ LL ans=1; for(int i=0;iint k=0; int t=n; while(t){ k+=t/prime[i]; t/=prime[i]; } ans=ans*poww(prime[i],k,mod)%mod; } cout<

热门文章