作者tw00088437 (喵猫 loves fish)
看板C_and_CPP
标题[问题] 求小於2^64整数立方根 问题:TLE
时间Wed Nov 18 20:05:34 2009
( *[1m *[m 为色码，可以按 Ctrl+V 预览会显示的颜色 )
( 未必需要依照此格式，文章条理清楚即可 )
遇到的问题： (题意请描述清楚)
TLE(10s)
希望得到的正确结果：
如何加速演算法
程式跑出来的错误结果：
开发平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
dev C++
有问题的code： (请善用置底文标色功能)
#include<iostream>
using namespace std;
int main()
{
unsigned long long n;
while(cin>>n)
{
if(!n)
break;
unsigned long long a=1;
while(a<=(n/a)/a)
{
if(a<=(n/a)/(a*1000000))
a*=100;
if(a<=(n/a)/(a*1000))
a*=10;
if(a<=(n/a)/(a*125))
a*=5;
if(a<=(n/a)/(a*27))
a*=3; //以上这麽一堆也不知道有没有比较快@@还是反而比较慢?
if(a<=(n/a)/(a*8))
a*=2;
a++;
}
printf("%d\n",a-1);
}
return 0;
}
补充说明：
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.228.105.160
1F：→ bleed1979:pow或cbrt？？ 11/18 20:08
2F：→ tw00088437:@@? 11/18 20:09
3F：→ tw00088437:我有看到你的70ms 囧 11/18 20:09
4F：推 zerodevil:先不管他变快还是变慢, 你的做法a一次至少要跳两倍 11/18 21:55
5F：→ zerodevil:所以在a>(答案/2)之後还是只能慢慢加 11/18 21:56
6F：→ zerodevil:就算会变快也没快多少 11/18 21:57
7F：推 ledia:试试二分法 ? 11/18 21:57
8F：推 delphi3:先设变数放n/a结果...少用除法 XD 11/19 01:53
9F：→ MOONRAKER:二分法会碰到overflow问题 XD 这题需要很多magic number 11/19 11:14
10F：推 ledia:二分法为什麽会 overflow ? @@ 11/19 14:22
11F：→ MOONRAKER:因为开始时会把rdelim设到ceil(cubic(longlong_max)+1) 11/19 16:13
12F：→ MOONRAKER:以求涵盖longlong_max…所以最後就检查输入是不是大於 11/19 16:14
13F：→ MOONRAKER:pow(ceil(cubic(longlong_max)), 3) 我到底在说啥 XD 11/19 16:15
14F：推 ledia:计算 (x+y)/2 可以用 x-(x-y)/2 来避免 overflow 11/19 23:27
15F：→ ledia:计算 boolean (a > n^3) 也可以化为 a/n/n > n 避免 11/19 23:27
16F：→ ledia:这样子二分法要的 operation 都有了 11/19 23:28
17F：→ MOONRAKER:其实後来拿掉比较rdelim和ldelim 11/20 01:06
18F：→ MOONRAKER:只比较(ldelim + rdelim)/2就不会overflow了 X( 11/20 01:07