大整数（number.???） [复制链接]

问题描述：
一个k（1≤k≤80）位的十进制正整数n，我们称其为大整数。现在的问题是，请你设计一个程序，对于给出的某一个大整数n，找到满足条件p3+p2+3p≤n的最大值。
输入数据：
输入文件是number.dat。该文件只有一行，是一个k位的大整数n。行首行末无多余空格。
输出数据：
输出文件是number.out。在文件的第一行输出你所找到的p的最大值。行首行末无多余空格。
输入输出示例：
number.dat 1000000000000001000000000000003000000000000001
number.out 1000000000000000

测试数据： number.rar (2 K) 下载次数:27

ddd

hard.....

我想二分枚举。

P的3方+2方.
有数学公式,但我忘了

帮你写了一个...
另: 数据 3 和 5 有问题, 笔算证实的 (除非题目理解问题)
#include <iostream>
#include <fstream>
#include <string>
// #include <conio.h>
using namespace std;

ifstream fin("number.dat");
ofstream fout("number.out");

string add(string a, string b)
{
    int lena=a.length(), lenb=b.length();
    if(lena<lenb)
    {
        swap(a,b);
        swap(lena,lenb);
    }
    if(lena>lenb)
    {
        string t;
        for(int i=1;i<=(lena-lenb);i++) t+='0';
        b=t+b;
    }
    a='0'+a; b='0'+b;
    for(int i=0;i<=lena;i++) a=a+b-48;
    for(int i=lena;i>0;i--)
        if(a>57)
        {
            a-=10;
            a[i-1]++;
        }
    if(a[0]=='0') a=a.substr(1,lena);
    return a;
}

string sub1(string a)
{
    int lena=a.length();
    if(a[lena-1]=='0')
    {
        a[lena-1]='9';
        a[lena-2]--;
        for(int i=lena-2;i>0;i--)
            if(a<'0')
            {
                a+=10;
                a[i-1]--;
            }
        if(a[0]=='0') a=a.substr(1,lena);
    }
    else
    {
        a[lena-1]--;
    }
    return a;
}

string mul(string a, char b)
{
    int lena=a.length();
    a='0'+a;
    for(int i=lena;i>0;i--)
    {
        a=(a-'0')*(b-'0');
    }
    for(int i=lena;i>0;i--)
    {
        a[i-1]+=(a)/10;
        a=(a%10)+'0';
    }
    if(a[0]=='0') a=a.substr(1,lena);
    return a;
}

string mul(string a, string b)
{
    int lena=a.length(), lenb=b.length();
    string ans;
    if(lena<lenb)
    {
        swap(a,b);
        swap(lena,lenb);
    }
    for(int i=0;i<lenb;i++)
    {
        ans+='0';
        ans=add(ans,mul(a,b));
    }
    return ans;
}

string calc(string p)
{
    string p2=mul(p,p);
    return add(mul(p2,p),add(mul(p,'3'),p2));
}

string div2(string a)
{
    int lena=a.length();
    string ans; int tmp=0,add;
    for(int i=0;i<lena;i++)
    {
        tmp=tmp*10+(a-'0');
        add=tmp/2;
        ans+=(add+'0');
        tmp-=add*2;
    }
    if(ans[0]=='0'&&ans.length()>1) ans=ans.substr(1,ans.length()-1);
    return ans;
}

int compare(string a, string b)
{
    int lena=a.length(), lenb=b.length();
    if(lena<lenb) return -1;
    else if(lena>lenb) return 1;
    else
    {
        for(int i=0;i<lena;i++)
        {
            if(a<b) return -1;
            else if(a>b) return 1;
        }
        return 0;
    }
}

int main()
{
    string n, result, low="0", mid, high="500000000000000000000000000"; // 5*10^26
    int opt;
    fin>>n;
    do
    {
        mid=add(div2(add(low,high)),"1");
        result=calc(mid);
        opt=compare(result,n);
        if(opt<0) low=mid;
        else if(opt>0) high=sub1(mid);
        // cout<<low<<" "<<mid<<" "<<high<<endl;
    } while(opt!=0&&compare(low,high)==-1);
    if(opt!=0) mid=low;
    fout<<mid<<endl;
    // getch();
}

引用第0楼hjwz于2007-07-12 21:50发表的 大整数（number.???） :
p3+p2+3p

不懂...

谁可以帮助我啊？？？？？？？？

题目看不懂