讨论 / 终于AC了!
outlaw 2011-10-16 13:43:00
点我顶贴 收藏 删除
这道题应该是用 二分 + 高精度

可是二分的right的界限应该定小一点(我之前就是因为这个总是超时)

我定的是 10^120 之后就能AC了

测试结果1: 通过本测试点|有效耗时391ms

测试结果2: 通过本测试点|有效耗时391ms

测试结果3: 通过本测试点|有效耗时500ms

测试结果4: 通过本测试点|有效耗时500ms

测试结果5: 通过本测试点|有效耗时515ms

测试结果6: 通过本测试点|有效耗时485ms

测试结果7: 通过本测试点|有效耗时484ms

测试结果8: 通过本测试点|有效耗时484ms

测试结果9: 通过本测试点|有效耗时485ms

测试结果10: 通过本测试点|有效耗时390ms

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cstring>

#include<string>

using namespace std;

const int size=8000;//最高定义8000位

struct hugeint

{

int len;

int num[size];

};

hugeint times(hugeint a, hugeint b)//乘法

{

hugeint ans;

memset(ans.num, 0, sizeof(ans.num));

for(int i = 1; i <= a.len; i++)

for(int j = 1; j <= b.len; j++)

ans.num[i+j-1] += a.num[i] * b.num[j];

for(int i = 1; i <= a.len + b.len; i++)

{

ans.num[i+1] += ans.num[i] / 10;

ans.num[i] %= 10;

}

if(ans.num[a.len + b.len] > 0)

ans.len = a.len + b.len;

else ans.len = a.len + b.len -1;

return ans;

}

hugeint add(hugeint a, hugeint b)//加法

{

hugeint ans;

memset(ans.num, 0, sizeof(ans.num));

ans.len = max(a.len, b.len);

for(int i = 1; i <= ans.len; i++)

{

ans.num[i] += a.num[i] + b.num[i];

ans.num[i + 1] += ans.num[i] / 10;

ans.num[i] %= 10;

}

if(ans.num[ans.len + 1] > 0)

ans.len++;

return ans;

}

hugeint average(hugeint a, hugeint b)

{

hugeint ans;

ans = add(a, b);

for(int i = ans.len; i >= 2; i--)

{

ans.num[i - 1] += (ans.num[i] % 2) * 10;

ans.num[i] /= 2;

}

ans.num[1] /= 2;

if(ans.num[ans.len] == 0)

ans.len--;

return ans;

}

int cmp(hugeint a, hugeint b)//a>b 返回1 b>a 返回-1 b==a返回0

{

if(a.len > b.len) return 1;

if(a.len < b.len) return -1;

for(int i = a.len; i >= 1; i--)

{

if(a.num[i] > b.num[i]) return 1;

if(a.num[i] < b.num[i]) return -1;

}

return 0;

}

void print(hugeint a)

{

for(int i = a.len; i >= 1; i--)

cout<<a.num[i];

cout<<endl;

}

hugeint t6(hugeint a)

{

hugeint ans=a;

for(int i = 1; i <= 6; i++)

ans=times(a,ans);

return ans;

}

int main()

{

// freopen("hugeint.in","r",stdin);

//freopen("hugeint.out","w",stdout);

string s;

cin>>s;

hugeint target,tmp;

memset(target.num,0,sizeof(target.num));

target.len=s.length();

for(int i = 1; i <= target.len; i++)

target.num[i]= s[target.len - i] - 48;//s的下标是从0开始的

hugeint left, right, mid;

left.len=1;

left.num[1]=1;

right.len=120;

right.num[120]=1;

while(1)

{

mid = average(left, right);

tmp = t6(mid);

if(cmp(tmp, target) == 1)

right = mid;

if(cmp(tmp, target) == -1)

left = mid;

if(cmp(tmp, target) == 0)

break;

}

print(mid);

return 0;

}

查看更多回复
提交回复