学步园

TAG 数论

求 max{ n | n! < 2^(2^k) },  其中k=(year-1960)/10+2;

阶乘结果会很大，所以两边取对数。log2(n!)=log2(n)*log2(n-1)*......*log2(1)

我是直接把所有结果求出来。

ps:

求阶乘的对数可以用

斯特林公式：
log10(n!) = log10(sqrt(2 * pi * n)) + n * log10(n / e)

不用累加，速度快。不过这里用不着，因为n不确定，我们要从头开始搜索。这里只是介绍一下这个公式而已。

答案：3 5 8 12 20 34 57 98 170 300 536 966 1754 3210 5910 10944 20366 38064 71421 134480 254016

/* source code of submission 426964, Zhongshan University Online Judge System */<br /> #include <stdio.h><br /> #include <math.h><br /> int p2[24];<br /> int ans[21];<br /> int n;<br /> void makepow2()<br /> {<br /> for (int i=0; i<24; ++i)<br /> {<br /> p2[i]=1 << i;<br /> }<br /> }<br /> int inpow2(int x)<br /> {<br /> int ret=1;<br /> for (int i=1; i<24; ++i)<br /> {<br /> if ( x>p2[i])<br /> {<br /> ret=i;<br /> }<br /> else<br /> {<br /> break;<br /> }<br /> }<br /> return ret-1;<br /> }<br /> void pre()<br /> {<br /> makepow2();<br /> double sum;<br /> for (int i=2; true; ++i )<br /> {<br /> sum+=log(i)/log(2);<br /> int tmp=inpow2( int( ceil(sum) ) );<br /> ans[tmp]=i;<br /> if ( tmp==21 )<br /> {<br /> return;<br /> }</p> <p> }<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> pre();<br /> while ( scanf("%d", &n)!=EOF && n!=0 )<br /> {<br /> printf("%d/n",ans[(n-1960)/10] );<br /> }<br /> return 0;<br /> }<br />