UVa 10916 Factstone Benchmark：数学及阶乘的处理技巧

UVa 10916 Factstone Benchmark：数学及阶乘的处理技巧2014-07-14 synapse7 10916 - Factstone Benchmark

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=99&page=show_problem&problem=1857

Amtel has announced that it will release a 128-bit computer chip by 2010, a 256-bit computer by 2020, and so on, continuing its strategy of doubling the word-size every ten years. （Amtel released a 64-bit computer in 2000, a 32-bit computer in 1990, a 16-bit computer in 1980, an 8-bit computer in 1970, and a 4-bit computer, its first, in 1960.）

Amtel will use a new benchmark - the Factstone - to advertise the vastly improved capacity of its new chips. The Factstone rating is defined to be the largest integern such that n！ can be represented as an unsigned integer in a computer word.

Given a year 1960 ≤ y ≤ 2160, what will be the Factstone rating of Amtel"s most recently released chip？

There are several test cases. For each test case, there is one line of input containing y. A line containing 0 follows the last test case. For each test case, output a line giving the Factstone rating.

Sample Input

196019810

Output for Sample Input

思路：字节数 k = （year - 1940） / 10, 问题就转化成 n ！ < 2 ^ k < （n + 1）！, 如果单纯模拟会溢出，所以我们对两边同取对数，因为log（a*b） = log（a） + log（b），所以log（n！） = sum（log（i））, （ 1<= i <= n）, 只要找到最小的sum（log（i）） > k * log（2），答案就是i- 1.

完整代码：

/*0.286s*/#include<cstdio>#include<cmath>const double log_2=log（2.0）;int main（void）{int year;while （scanf（"%d", &year）, year）{int n = （year - 1940） / 10;double k = pow（2, n） * log_2, sum = 0;for （int i = 1;; i++）{sum += log（i）;if （sum > k）{printf（"%d
", i - 1）;break;}}}return 0;}

打表：

/*0.012s*/#include<cstdio>const int ans[21] ={3, 5, 8, 12, 20,34, 57, 98, 170,300, 536, 966, 1754,3210, 5910, 10944, 20366,38064, 71421, 134480, 254016};int main（void）{int year;while （scanf（"%d", &year）, year）printf（"%d
", ans[（year - 1960） / 10]）;}