开发平台(Platform): (Ex: Win10, Linux, ...)
Windows 10
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
g++
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
问题(Question)：
如何改善此题的计算速度
喂入的资料(Input)：
2200
预期的正确结果(Expected Output)：
166057045
错误结果(Wrong Output)：
计算时间过长
程式码(Code)：(请善用置底文网页, 记得排版，禁止使用图档)
#include<iostream>
#include<cmath>
#include<ctime>
using namespace std;
int main()
{
int year;
while(cin >> year)
{
double x = clock();
double bits = pow(2 , (year-1900)/10 ) * 4 * log(2);
double sum = 0;
unsigned int n;
for(n = 1 ; sum < bits ; ++n)
{
sum += log(n);
}
cout << n-2 << " ," << (clock() - x)/1000.0 << "s \n" ;
}
return 0;
}
补充说明(Supplement)：
题目说明：
Suppose a CPU with a k-bit can compute a maximum integer of (2^k) - 1, and
every 10 years k will grow by a multiple of 2. Suppose that your company
first released a 4-bit CPU in 1900, and the largest integer of its operation
is 15 (so 8bits will be released in 1910, and 1920 is 16 bits... and so on).
Now given the year Y, find a maximum positive integer N, so that N! is within
the CPU calculation range of the current year.
Test time limit: 5.0 seconds
已知 1900年已有 4bits CPU,可计算范围为 2^4-1,请问当 Y年, N!为该年CPU可计算之最
大范围，请问 N的最大值为何?
Input:
正整数 Y, 2200 >= Y >= 1900
Output:
N
Sample:
1900 => 3
1910 => 5
2097 => 134480
想法:
因为每10年倍数会增为2倍，故以2^((Year-1900)/10)算出成长几倍，乘上一开始
的 4bit。输入2200时，最大计算范围约为 2^(2^32)-1。因为超过基本型别能存的范围，所
以我想到用 log 做处理，
令 N! < 2^(2^32) , 则 log N! < log 2^(2^32) = 2^32 * log(2)，
又 log N! = log 1 + log 2 + log 3 + ... log N
所以用for循环累加判断。有学长提到可以用积分的方式计算，但是目前还没有想法，想请教
版上的前辈是否能指点一下? 目前执行时间约在 3.8 ~ 4.1 second，虽然在题目要求的区间
，但想了解该题计算时，是否有更有效的做法。