首页 > 代码库 > BZOJ 3000(Big Number-Stirling公式求n!近似值)
BZOJ 3000(Big Number-Stirling公式求n!近似值)
3000: Big Number
Time Limit: 2 Sec Memory Limit: 128 MBSubmit: 220 Solved: 62
[Submit][Status]
Description
给你两个整数N和K,要求你输出N!的K进制的位数。
Input
有多组输入数据,每组输入数据各一行,每行两个数——N,K
Output
每行一个数为输出结果。
Sample Input
2 5
2 10
10 10
100 200
2 10
10 10
100 200
Sample Output
1
1
7
69
对于100%的数据,有2≤N≤2^31, 2≤K≤200,数据组数T≤200。
1
7
69
对于100%的数据,有2≤N≤2^31, 2≤K≤200,数据组数T≤200。
HINT
Source
本题需要用到Stirling公式
∴位数=log10(n!)+1
方案1:[WA]n!不断div k
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; typedef long double ld; ld log(ll a,int b){} int main() { // freopen("bzoj3000.in","r",stdin); // freopen(".out","w",stdout); ll n;int k; while (scanf("%lld%d",&n,&k)!=EOF) { if (n<=10000) { ll ans=0,p=1; Fork(i,2,n) { p*=i; while (p>=k) {p/=k,ans++;} cout<<i<<':'<<p<<' '<<ans<<endl; } if (p) ans++; printf("%lld\n",ans); } } return 0; }但是这样做是错的。TNT
理由是不断div k 会把原来小的部分删掉
方案2:logk(n!)=log(1)+log(2)+...+log(n)
效率为O(n),显然也不行
于是不妨用Stirling公式求近似值
位数=logk(n!)+1
≈ logk(sqrt(2πn)*(n/e)^n+1
= logk(sqrt(2πn))+log[(n/e)^n]+1
=1/2*logk(2πn)+nlog(n/e)+1
=0.5*logk(2πn)+nlog(n/e)+1
=0.5*logk(2πn)+nlog(n)-nlog(e)+1
PS:pi=acos(-1.0),e=exp(1)
PS2:eps的存在是为了防止n=2,k=2这样刚好的情况出现,这个时候向上取整要多取1位
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMI(a) memset(a,127,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; typedef long double ld; ld const pi=acos(-1.0),e=exp(1),eps=1e-10; ld log(ld a,ld b){return log(a)/log(b);} int main() { // freopen("bzoj3000.in","r",stdin); // freopen(".out","w",stdout); ll n;int k; cout.setf(ios::fixed); cout.precision(0); while (scanf("%lld%d",&n,&k)!=EOF) { if (n<=10000) { ld ans=0.0; For(i,n) ans+=log(i); ans/=log(k); ans=ceil(ans+eps); cout<<ans<<endl; } else { cout<<ll(0.5*log(2*pi*n,k)+n*log(n,k)-n*log(e,k))+1<<endl; } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。