大数阶乘的常规运算

即数学的模拟运算。一位一位的乘,有进位就进位。
#include <bits/stdc++.h> #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<<a[i]; cout<<endl; } }
引例之速求阶乘末尾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 <bits/stdc++.h> 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<<ans<<endl; 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 <bits/stdc++.h> #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
;i<cnt && prime[i]<=n;i++){int k=0; int t=n; while(t){ k+=t/prime[i];
t/=prime[i]; } ans=ans*poww(prime[i],k,mod)%mod; }cout<<ans<<endl; } }

友情链接
ioDraw流程图
API参考文档
OK工具箱
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:637538335
关注微信