题解 - Vijos

1

Sky1231 (sky1231) LV 10 @ 2020-10-14 19:10:28

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct ubigint
{
    vector<int> num;
    int operator == (ubigint b)
    {
        if (num.size()!=b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
                if (num[i]!=b.num[i])
                    return 0;
            return 1;
        }
    }
    int operator != (ubigint b)
    {
        return ((!(*this==b))?1:0);
    }
    int operator < (ubigint b)
    {
        if (num.size()<b.num.size())
            return 1;
        else if (num.size()>b.num.size())
            return 0;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
            {
                if (num[size-1-i]<b.num[size-1-i])
                    return 1;
                else if (num[size-1-i]>b.num[size-1-i])
                    return 0;
            }
            return 0;
        }
    }
    int operator > (ubigint b)
    {
        if (num.size()<b.num.size())
            return 0;
        else if (num.size()>b.num.size())
            return 1;
        else
        {
            for (unsigned long long i=0,size=num.size();i<size;i++)
            {
                if (num[size-1-i]<b.num[size-1-i])
                    return 0;
                else if (num[size-1-i]>b.num[size-1-i])
                    return 1;
            }
            return 0;
        }
    }
    int operator <= (ubigint b)
    {
        return ((!(*this>b))?1:0);
    }
    int operator >= (ubigint b)
    {
        return ((!(*this<b))?1:0);
    }
    ubigint mov(long long x)
    {
        ubigint ans;
        ans.num.clear();
        if (x+num.size()>0)
        {
            ans.num.resize(num.size()+x,0);
            for (long long i=0,size=num.size();i<size;i++)
                if (i+x>=0)
                    ans.num[i+x]=num[i];
        }
        else
            ans=0;
        return ans;
    }
    ubigint operator = (long long b)
    {
        char s[20+1];
        sprintf(s,"%lld",b);
        num.clear();
        num.resize(strlen(s));
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(s[size-1-i]-'0');
        return (*this);
    }
    ubigint operator = (string b)
    {
        num.clear();
        num.resize(b.size());
        for (unsigned long long i=0,size=num.size();i<size;i++)
            num[i]=(b[size-1-i]-'0');
        return (*this);
    }
    ubigint operator + (ubigint b)
    {
        ubigint ans;
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)+((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
        {
            if (ans.num[i]>=10&&i==size-1)
                ans.num.resize(++size);
            ans.num[i+1]+=(ans.num[i]/10);
            ans.num[i]%=10;
        }
        return ans;
    }
    ubigint operator += (ubigint b)
    {
        return (*this=(*this+b));
    }
    ubigint operator - (ubigint b)
    {
        ubigint ans;
        if ((*this)==b)
        {
            ans=0;
            return ans;
        }
        ans.num.clear();
        ans.num.resize(max(num.size(),b.num.size()));
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            ans.num[i]=((i<num.size())?num[i]:0)-((i<b.num.size())?b.num[i]:0);
        for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            while (ans.num[i]<0)
                ans.num[i]+=10,ans.num[i+1]--;
        while (ans.num[ans.num.size()-1]==0)
            ans.num.resize(ans.num.size()-1);
        return ans;
    }
    ubigint operator -= (ubigint b)
    {
        return (*this=(*this-b));
    }
    ubigint tm (ubigint b,unsigned long long pos)
    {
        ubigint ans,num_0;
        num_0=0;
        ans.num.clear();
        if (*this!=num_0&&b!=num_0)
        {
            ans.num.resize(num.size()+pos);
            for (unsigned long long i=0,size=num.size();i<size;i++)
                ans.num[i+pos]=num[i]*b.num[pos];
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
        }
        else
            ans=0;
        return ans;
    }
    ubigint operator * (ubigint b)
    {
        ubigint ans,num_0;
        ans=0,num_0=0;
        ans.num.clear();
        if (*this!=num_0&&b!=num_0)
        {
            for (unsigned long long i=0,size=b.num.size();i<size;i++)
                ans+=(*this).tm(b,i);
        }
        return ans;
    }
    ubigint operator *= (ubigint b)
    {
        return (*this=(*this*b));
    }
    ubigint operator / (ubigint b)
    {
        ubigint ans,num_0;
        num_0=0;
        if (*this<b)
            return num_0;
        if (*this!=num_0&&*this>num_0)
        {
            ubigint x,y;
            x=*this,y=b.mov(num.size()-b.num.size());
            ans.num.resize(num.size()-b.num.size()+1,0);
            for (long long i=ans.num.size()-1;i>=0;i--,y=y.mov(-1))
                while (x>=y)
                    x-=y,ans.num[i]++;
            for (unsigned long long i=0,size=ans.num.size();i<size;i++)
            {
                if (ans.num[i]>=10&&i==size-1)
                    ans.num.resize(++size);
                ans.num[i+1]+=(ans.num[i]/10);
                ans.num[i]%=10;
            }
            while (ans.num.size()>1&&ans.num[ans.num.size()-1]==0)
                ans.num.resize(ans.num.size()-1);
        }
        else
            ans=0;
        return ans;
    }
    ubigint operator /= (ubigint b)
    {
        return (*this=(*this/b));
    }
    void print()
    {
        for (unsigned long long i=0,size=num.size();i<size;i++)
            printf("%d",num[size-1-i]);
    }
};

char s[100];
string ss;

int main()
{
    while (~scanf("%s",s))
    {
        ss=s;
        ubigint l,r,n,num1,num2,num3,sum,temp;
        l=0,r=n=ss,num1=1,num2=2,num3=3;
        for (ubigint mid;r-l>num1;)
        {
            mid=(l+r)/num2;
            temp=mid*mid;
            sum=mid*temp+temp+num3*mid;
            if (sum<n)
                l=mid;
            else if (sum>n)
                r=mid;
            else
                l=r=mid;
        }
        temp=r*r;
        sum=r*temp+temp+num3*r;
        if (sum<=n)
        {
            r.print();
            printf("\n");
            continue;
        }
        temp=l*l;
        sum=l*temp+temp+num3*l;
        if (sum<=n)
        {
            l.print();
            printf("\n");
            continue;
        }
    }
}

0

caonh3cu LV 5 @ 2021-12-14 19:47:11

from decimal import Decimal
a=int(input())
if a<=2:
print(0)
else:
b = int(a ** Decimal('0.33333333333333333333333333333333333333333333333333333333333333333333333333333333'))
if b*(b*(b+1)+3)>a:
print(b-1)
else:
print(b)

0

2585479524 LV 7 @ 2020-03-08 21:18:01

这题用C++怕是要手撸大数加减乘除，但是java自带的大数类就不一样了

import java.math.*;
import java.util.*;
public class Main {
    static BigInteger num;
    public BigInteger bSearch(BigInteger k)
    {
        BigInteger mid,left=BigInteger.valueOf(0),right=k;
        BigInteger one=BigInteger.valueOf(1);
        BigInteger two=BigInteger.valueOf(2);
        BigInteger three=BigInteger.valueOf(3);
        BigInteger temp;
        while(left.compareTo(right)<=0)
        {
            mid=(left.add(right).divide(two));
            temp=mid.pow(3).add(mid.pow(2)).add(mid.multiply(three));
            if(temp.compareTo(k)>0) right=mid.subtract(one);
            else left=mid.add(one);
        }
        return right;
    }
    public static void main(String[] args)  {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext())
        {
            num=cin.nextBigInteger();
            Main t=new Main();
            BigInteger ans=t.bSearch(num);
            System.out.println(ans);
        }
    }
}

0

sumshine LV 6 @ 2018-11-08 20:51:18


def main():
    number = int(input())
    left = 0
    right = number
    while left < right:
        mid = left + (right - left) // 2
        if mid == left:
            break
        if mid*mid*mid + mid*mid + mid*3 <= number:
            left = mid
        else:
            right = mid 
    print(left)

main()

w568w @ 2019-10-13 12:27:42

酱真...这高精度题用python等于作弊

0

liuyiah LV 10 @ 2016-08-16 16:47:31

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 105;

struct bign
{
    int len, s[MAXN];
    bign ()
    {
        memset(s, 0, sizeof(s));
        len = 1;
    }
    bign (int num) { *this = num; }
    bign (const char *num) { *this = num; }
    bign operator = (const int num)
    {
        char s[MAXN];
        sprintf(s, "%d", num);
        *this = s;
        return *this;
    }
    bign operator = (const char *num)
    {
        for(int i = 0; num[i] == '0'; num++) ;  //去前导0
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }
    bign operator + (const bign &b) const //+
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++)
        {
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b)
    {
        *this = *this + b;
        return *this;
    }
    void clean()
    {
        while(len > 1 && !s[len-1]) len--;
    }
    bign operator * (const bign &b) //*
    {
        bign c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++)
        {
            for(int j = 0; j < b.len; j++)
            {
                c.s[i+j] += s[i] * b.s[j];
            }
        }
        for(int i = 0; i < c.len; i++)
        {
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }
    bign operator *= (const bign &b)
    {
        *this = *this * b;
        return *this;
    }
    bign operator - (const bign &b)
    {
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++)
        {
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];
            if(x >= 0) g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator -= (const bign &b)
    {
        *this = *this - b;
        return *this;
    }
    bign operator / (const bign &b)
    {
        bign c, f = 0;
        for(int i = len-1; i >= 0; i--)
        {
            f = f*10;
            f.s[0] = s[i];
            while(f >= b)
            {
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;
        c.clean();
        return c;
    }
    bign operator /= (const bign &b)
    {
        *this  = *this / b;
        return *this;
    }
    bign operator % (const bign &b)
    {
        bign r = *this / b;
        r = *this - r*b;
        return r;
    }
    bign operator %= (const bign &b)
    {
        *this = *this % b;
        return *this;
    }
    bool operator < (const bign &b)
    {
        if(len != b.len) return len < b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const bign &b)
    {
        if(len != b.len) return len > b.len;
        for(int i = len-1; i >= 0; i--)
        {
            if(s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const bign &b)
    {
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const bign &b)
    {
        return !(*this == b);
    }
    bool operator <= (const bign &b)
    {
        return *this < b || *this == b;
    }
    bool operator >= (const bign &b)
    {
        return *this > b || *this == b;
    }
    string str() const
    {
        string res = "";
        for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
        return res;
    }
};

istream& operator >> (istream &in, bign &x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out, const bign &x)
{
    out << x.str();
    return out;
}

int main()
{
    ios::sync_with_stdio(false);
    bign n,left,right,mid;
    cin >> n;
    if (n==0) {
        putchar('0');
        return 0;
    }
    left=0;right=n;
    while (left<right){
        mid=(left+right)/2;
        if (mid==left){
            cout << left;
            return 0;
        }
        if (mid*mid*mid+mid*mid+mid+mid+mid<=n) left=mid;
        else right=mid;
    }
    return 0;
}

0

chronix LV 8 @ 2016-07-19 17:03:32

#include <cstdio>
#include <cstring>

int N[50]={0};

int read(int a[]){
char c[10000];
scanf("%s",c);
int n=1,len=strlen(c),k=1;
for(int i=0;i<len;i++){
if(k==10000){
k=1;
n++;
}
a[n]+=k*(c[len-i-1]-'0');
k*=10;
}
a[0]=n;
}

int addx(int a[],int b[],int c[]){
int len=a[0]>b[0]?a[0]:b[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]+b[i];
c[i+1]+=c[i]/10000;
c[i]%=10000;
}
len++;
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

void multx(int a[],int b[],int c[]){
for(int i=1;i<=a[0];i++)
for(int j=1;j<=b[0];j++){
c[i+j-1]+=a[i]*b[j];
c[i+j]+=c[i+j-1]/10000;
c[i+j-1]%=10000;
}
int len=a[0]+b[0];
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

void add(int a[],int x){
int temp,k;
temp=a[1]+x;
k=temp/10000;
a[1]=temp%10000;
int len=a[0];
for(int i=2;i<=a[0]||k;i++){
temp=a[i]+k;
k=temp/10000;
a[i]=temp%10000;
len=i;
}
while(a[len]==0&&len>1)
len--;
a[0]=len;
}

void mult(int a[],int x){
int len,temp,k=0;
for(int i=1;i<=a[0]||k;i++){
temp=a[i]*x+k;
k=temp/10000;
a[i]=temp%10000;
len=i;
}
while(a[len]==0&&len>1)
len--;
a[0]=len;
}

int bigger(int a[],int b[]){
if(a[0]!=b[0])
return a[0]>b[0];
int flag=999;
for(int i=a[0];i>=1;i--)
if(a[i]!=b[i]){
flag=a[i]>b[i];
break;
}
if(flag==999)
return 0;
return flag;
}

int minusx(int a[],int b[],int c[]){
int len=a[0];
for(int i=1;i<=len;i++){
c[i]+=a[i]-b[i];
if(c[i]<0){
c[i]+=10000;
c[i+1]-=1;
}
}
while(c[len]==0&&len>1)
len--;
c[0]=len;
}

void div(int c[1111],int x) {
for(int i=c[0]; i>=1; i--) {
if(c[i]%x!=0)
c[i-1]+=(c[i]%x)*10000;
c[i]/=x;
}
while(c[c[0]]==0&&!c[0]==1)
c[0]--;
}

void output(int a[]){
printf("%d",a[a[0]]);
for(int i=a[0]-1;i>=1;i--)
printf("%04d",a[i]);
}

//p^3+p^2+3p
void getans(int p[1111],int re[1111]){
int p3[1111]={0},p2[1111]={0},p1[1111]={0};
int temp[1111];

memset(temp,0,sizeof(temp));
multx(p,p,p3);
multx(p,p3,temp);
memcpy(p3,temp,sizeof(temp));

multx(p,p,p2);

memcpy(p1,p,sizeof(p1));
mult(p1,3);

memset(temp,0,sizeof(temp));
addx(p3,p2,temp);
addx(temp,p1,re);
}

int great(int a[1111],int b[1111]){
int r1[1111]={0};
getans(a,r1);
return bigger(r1,b);
}

int answer[1111];

int low[1111]={1,0};
int high[1111]={8,9999,9999,9999,9999,9999,9999,9999,9999};

int search(){
int mid[1111];
while(!bigger(low,high)){
memset(mid,0,sizeof(mid));
addx(low,high,mid);
if(mid[1]%2==1)
mid[1]--;
div(mid,2);
if(great(mid,N)){
int m[1111]={1,1};
int re[1111]={0};
minusx(mid,m,re);
memcpy(high,re,sizeof(re));
}
else
if(great(N,mid)){
memcpy(low,mid,sizeof(mid));
add(low,1);
memcpy(answer,mid,sizeof(mid));
}
else{
memcpy(answer,mid,sizeof(mid));
return 666;
}
}
return 888;
}

int main(){
//freopen("in.txt","r",stdin);
read(N);
search();
output(answer);
return 0;
}

0

Accepted! LV 10 @ 2016-07-15 13:46:33

二分+高精度集合
三次rp积累

Accepted! @ 2016-07-15 13:46:47

146行代码

0

651291702@qq.com LV 8 @ 2016-05-11 17:17:39

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=500;
#define clp(s,ss)  memcpy(s,ss,sizeof(ss)) 
char pr[N];
int a[N],b[N],c1[N],c2[N],c3[N],d[N],f[N],s[N],ans[N];
void cls(int h[])
{    for(int i=1;i<=h[0];i++)  h[i]=0;h[0]=0;}
void init()
{
     scanf("%s",pr); b[0]=strlen(pr); 
     for(int i=1;i<=b[0];i++)   b[i]=pr[b[0]-i]-'0'; 
     clp(f,b);  a[0]=1;a[1]=1;  d[0]=1;d[1]=3;
     ans[0]=1;ans[1]=0;
}
void to_to(int h[],int len)
{
     for(int i=1;i<=len+1;i++)
         {
             h[i+1]+=h[i]/10;
             h[i]%=10;
         }
    int pos;
    for(pos=len+2;h[pos]==0;pos--);  h[0]=pos;
    return ;
}
void add(int h1[],int h2[],int h3[])
{  
     int len=max(h2[0],h3[0]);
     for(int i=1;i<=len;i++)  h1[i]=h2[i]+h3[i];
     to_to(h1,len);  
}
void chu(int h[])
{
     int sum=0; if(h[1]%2!=0) h[1]--;
     for(int i=h[0];i>=1;i--)    
       {
          sum=sum*10+h[i];
          h[i]=sum/2;
          sum%=2;     
       } 
       int i;
     for(i=h[0]+2;h[i]==0;i--);h[0]=i;
}
bool pd(int h1[],int h2[])
{
     if(h1[0]<h2[0]) return true;
     if(h1[0]>h2[0]) return false;
     for(int i=h1[0];i>=1;i--)  
     {
          if(h1[i]>h2[i]) return false;
          if(h1[i]<h2[i]) return true;
     }
     return true;   
}
void add_(int h[],int num)
{
        h[1]+=num;
        to_to(h,h[0]);
}
void chen(int h3[],int h1[],int h2[])
{
    cls(h3);
     for(int i=1;i<=h1[0];i++)
        for(int j=1;j<=h2[0];j++)
           h3[i+j-1]+=h1[i]*h2[j];
    to_to(h3,h1[0]+h2[0]+1);
}
bool solve(int h[])
{
     chen(s,d,h);
     chen(c2,h,h);
     if(c2[0]>f[0]) return false;
     add(s,s,c2);
     chen(c3,c2,h);
     if(c3[0]>f[0]) return false;
     add(s,s,c3);
     if(pd(s,f)) return true;
     else return false;
}
int main()
{
    init();
    while(pd(a,b)) 
     {
        add(c1,a,b);chu(c1);  
         if(solve(c1)) {clp(ans,c1);clp(a,c1);add_(a,1);}
         else {clp(b,c1);add_(b,-1);}
     }
     for(int i=ans[0];i>=1;i--) printf("%d",ans[i]);
     return 0;
}

0

BH_2 LV 8 @ 2016-03-26 20:04:54

def f(x):
    return x*x*x+x*x+3*x
num=int(input())
left=0;
right=num;
mid=0;
mark=0
while left<right:
    mid=int((left+right)/2)
    #print("midzhi ",mid)
    fx=f(mid)
    if fx==num:
        ans=mid
        mark=1
        break
    elif fx>num:
        right=mid 
    else:
        left=mid+1
if mark==0:
    ans=left-1
print(ans)

0

BH_2 LV 8 @ 2016-03-26 20:04:27

def f(x):
return x*x*x+x*x+3*x
num=int(input())
left=0;
right=num;
mid=0;
mark=0
while left<right:
mid=int((left+right)/2)
#print("midzhi ",mid)
fx=f(mid)
if fx==num:
ans=mid
mark=1
break
elif fx>num:
right=mid
else:
left=mid+1
if mark==0:
ans=left-1
print(ans)

0

wang_yanheng LV 10 @ 2015-05-24 21:48:25

大爱python

def f(x):
return x*x*x+x*x+3*x
num=int(raw_input())
left=0
right=num
mid=0
while left<right-1:
mid=(left+right)/2
fx=f(mid)
if fx==num:
break
elif fx>num:
right=mid
else:
left=mid
if f(mid)<=num:
print mid
else:
print left

0

Sam.H.X LV 6 @ 2014-08-20 19:58:03

二分而已，水题，高精度数组一定要开大。
###Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXN=100+5;
struct bign
{
int len,s[MAXN];
bign() { memset(s,0,sizeof(s)); len=1; }

bign operator = (const char* num)
{
// for(int i=0;num[i]=='0';num++);
len=strlen(num);
for(int i=0;i!=len;++i) s[i]=num[len-i-1]-'0';
return *this;
}
bign operator = (const int num)
{
char s[MAXN];
sprintf(s,"%d",num);
*this = s;
return *this;
}
bign(int num) { this=num; }
bign(const char num) { *this=num; }

string str() const
{
string res="";
for(int i=0;i!=len;++i) res=static_cast<char>(s[i]+'0')+res;
if(res=="") res="0";
return res;
}
void clean()
{
while(len>1 && !s[len-1]) len--;
}

bign operator + (const bign& b) const
{
bign c;
c.len=0;
for(int i=0,g=0;g||i!=max(len,b.len);++i)
{
int x=g;
if(i<len) x+=s[i];
if(i<b.len) x+=b.s[i];
c.s[c.len++]=x%10;
g=x/10;
}
return c;
}
bign operator += (const bign& b)
{
*this=*this+b;
return *this;
}

bign operator * (const bign& b)
{
bign c;
c.len=len+b.len;
for(int i=0;i!=len;++i)
for(int j=0;j!=b.len;++j)
c.s[i+j]+=s[i]*b.s[j];
for(int i=0;i!=c.len;++i)
{
c.s[i+1]+=c.s[i]/10;
c.s[i]%=10;
}
c.clean();
return c;
}
bign operator *= (const bign& b)
{
*this=*this*b;
return *this;
}

bign operator - (const bign& b)
{
bign c;
c.len=0;
for(int i=0,g=0;i!=len;++i)
{
int x=s[i]-g;
if(i<b.len) x-=b.s[i];
if(x>=0) g=0;
else
{
g=1;
x+=10;
}
c.s[c.len++]=x;
}
c.clean();
return c;
}
bign operator -= (const bign& b)
{
*this=*this-b;
return *this;
}

bign operator / (const bign& b)
{
bign c,f=0;
for(int i=len-1;i>=0;--i)
{
f=f*10;
f.s[0]=s[i];
while(f>=b)
{
f-=b;
c.s[i]++;
}
}
c.len=len;
c.clean();
return c;
}
bign operator /= (const bign& b)
{
*this=*this/b;
return *this;
}

bign operator % (const bign& b)
{
bign r=*this/b;
r=*this-r*b;
return r;
}
bign operator %= (const bign& b)
{
*this=*this%b;
return *this;
}

bool operator < (const bign& b) const
{
if(len!=b.len) return len<b.len;
for(int i=len-1;i>=0;--i)
if(s[i]!=b.s[i]) return s[i]<b.s[i];
return false;
}
bool operator > (const bign& b) const
{
if(len!=b.len) return len>b.len;
for(int i=len-1;i>=0;--i)
if(s[i]!=b.s[i]) return s[i]>b.s[i];
return false;
}

bool operator == (const bign& b) const
{
return !(*this>b) && !(*this<b);
}

bool operator != (const bign& b) const
{
return (*this>b) || (*this<b);
}

bool operator <= (const bign& b) const
{
return (*this<b) || (*this==b);
}
bool operator >= (const bign& b) const
{
return (*this>b) || (*this==b);
}

};

istream& operator >> (istream &in,bign& x)
{
string s;
in>>s;
x=s.c_str();
return in;
}
ostream& operator << (ostream &out,const bign& x)
{
out<<x.str();
return out;
}
bign zero=0,one=1,three=3;
bign n;

void b_s(bign a,bign b)//binary search
{
if(b==zero)
{
cout<<0<<endl;exit(0);
}
while(b>a)
{
bign mid=(a+b)/2;
if(a==mid)
{
cout<<a<<endl;exit(0);
}
// cout<<"A="<<a<<" B="<<b<<endl;
if(mid*mid*mid+mid*mid+three*mid<=n) a=mid;
else b=mid;
}
}

int main()
{
zero.len=one.len=three.len=1;
cin>>n;
b_s(zero,n);
return 0;
}

0

tommyzong LV 8 @ 2013-08-13 11:25:06

###
from decimal import Decimal
q=Decimal(input())
b=q**Decimal('0.33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333')
b=int(b)
if b**3+b**2+b*3>q:
print(b-1)
else:
print(b)

lemontree712 @ 2014-01-25 22:16:29

Python好简单！！

0

tommyzong LV 8 @ 2013-08-13 11:22:39

python：
'''python
from decimal import Decimal
q=Decimal(input())
b=q**Decimal('0.33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333')
b=int(b)
if b**3+b**2+b*3>q:
print(b-1)
else:
print(b)
'''

0

wyc4662 LV 10 @ 2010-07-17 21:41:45

来晚了，124个AC

特别感谢ether大牛赐予思路……

此题竟然耗了2个半晚上

68行AC！

---|---|---|---|---|---|---|---|---|---|-

近一年后发现题解都没更新，而且人数也才130，这道题真的那么难么，我这个菜鸟都A了……

晒一下代码，再次感谢一下ether大牛：

var n,a2,c:array[1..100] of integer;

i,j,m:integer;

c2:char;

ch:boolean;

function work(o:integer):boolean;

var k,t:integer;

a,b,c,d:array[1..6500] of integer;

begin

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

fillchar(c,sizeof(c),0);

fillchar(d,sizeof(d),0);

for k:=1 to i do

for t:=1 to i do begin

b[t+k-1]:=a2[k]*a2[t]+b[t+k-1];

b[t+k]:=b[t+k]+b[t+k-1] div 10;

b[t+k-1]:=b[t+k-1] mod 10;

if (t+k-1>80) and (b[t+k-1]0) then exit(true);

end;

for k:=1 to i do

for t:=1 to i do begin

a[t+k-1]:=a2[k]*b[t]+a[t+k-1];

a[t+k]:=a[t+k]+a[t+k-1] div 10;

a[t+k-1]:=a[t+k-1] mod 10;

if (t+k-1>80) and (a[t+k-1]0) then exit(true);

end;

for k:=1 to i do begin

c[k]:=a2[k]*3+c[k];

c[k+1]:=c[k+1]+c[k] div 10;

c[k]:=c[k] mod 10;

end;

for k:=1 to 80 do begin

d[k]:=a[k]+b[k]+c[k]+d[k];

d[k+1]:=d[k+1]+d[k] div 10;

d[k]:=d[k] mod 10;

end;

for k:=80 downto 1 do

if d[k]>n[k] then exit(true) else

if d[k]30 then m:=30 else m:=i;

for j:=m downto 1 do begin

repeat

a2[j]:=a2[j]+1;

if a2[j]>9 then break;

until work(a2[j]);

a2[j]:=a2[j]-1;

end;

for i:=80 downto 1 do begin

if ch then write(a2[i]) else

if a2[i]0 then begin

ch:=true;

write(a2[i]);

end;

end;

if not ch then write(0);

end.

0

mike_nzk LV 10 @ 2009-09-13 09:43:31

高精开立方根爽极了！！！

设f(p)=p^3+p^2+3p

p^3

0

OIWinner LV 10 @ 2009-08-20 14:24:50

哎,GDOI的题啊。。。。。。

0

zxhzxh LV 10 @ 2009-08-11 16:46:06

高位推低位，再加二分，效果相当好

再编个高精，应该没问题了

0

why19931123 LV 10 @ 2009-07-25 20:51:00

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

二分!!!!!!!

0

boyzkk LV 10 @ 2009-07-15 18:14:57

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

如此水题。。。二分即可。

题解

49 条题解

大整数

信息

状态

开发

支持

题解

49 条题解

大整数

信息

状态

开发

支持

还没有账户？

登录