可是二分的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;
}