→ bibo9901: 只有21種可能..建表 03/15 03:17
推 s4300026: 樓上推文使我想起ACM有一題要我做質因數分解，也是建質 03/15 08:15
→ s4300026: 數表才不會TLE 03/15 08:15
推 zamperla: 昨天的作業hehe 03/15 10:24
→ FRAXIS: 這行嗎 03/15 11:28
開發平台(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，雖然在題目要求的區間
，但想了解該題計算時，是否有更有效的做法。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.118.142.132
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1552588788.A.3F8.html