大整数开根

2017年02月23日 15点热度 0人点赞 0条评论
#include
#include
#include
using namespace std;
void bigchen(char* a,char* b,char *c){
    int t[1000]={0},la=strlen(a),lb=strlen(b),i,j;
    for(i=0;i9){
            t[i+1]+=t[i]/10;
            t[i]%=10;
        }
        }
        int k=la+lb;
        while(t[k]!=0){
                if(t[k]>9){
                    t[k+1]+=t[k]/10;
                    t[k]%=9;
                }
            k++;
        }
        for(i=k-1;i>=1;i--)
            c[k-1-i]=t[i]+'0';
        c[k-1]=0;
}
bool cmp(char *a,char *ans,int pos){ 
    int la=strlen(a);
    if(la!=pos) return la>pos;
    return  memcmp(a,ans,pos*sizeof(char))>0;
}
void bigsqrt(char* a,char *ans){
    int la=strlen(a),k,i,j;
    char t[1000];
    if(la%2==0)
        k=la/2;
    else
        k=la/2+1;
   ans[k]=0;
    for(i=0;i

下面是效率高,某大神的代码

//By Cappuccino
#include 
#include 

int l;
int work(int o,char *O,int I)
{
char c, *D=O ;
if(o>0)
{
for(l=0;D[l];D[l++]-=10)
{
D[l++]-=120;
D[l]-=110;
while(!work(0,O,l))
D[l]+=20;
putchar((D[l]+1032)/20);
}
putchar(10);
}
else
{
c=o+(D[I]+82)%10-(I>l/2)*(D[I-l+I]+72)/10-9;
D[I]+=I<0 ? 0 : !(o=work(c/10,O,I-1))*((c+999)%10-(D[I]+92)%10);
}
return o;
}

int main()
{
char s[1200];s[0]='0';
scanf("%s",s+1);
if(strlen(s)%2 == 1)
work(2,s+1,0);
else
work(2,s,0);
return 0;
}

下面效率更高

#include 

#include 

using namespace std;



int compare(char* a, char* c, int la, int lb, int lc, int i)

{

if (la - 2 * (lb - i) >= lc)

return 1;

else if (la - 2 * (lb - i) + 1 < lc)

return 0;

else

{

for (int j = 0; j <= lc; j++)

{

if (a[la - j - 1] > c[j])

return 1;

else if (a[la - j - 1] < c[j])

return 0;

}

return 1;

}

}



int main()

{

char* b = new char[1000];

int la = 0;

cin >> b;

while (b[la] != '')

la++;

char* a = new char[la], *c;

for (int i = 0; i < la; i++)

a[i] = b[la - i - 1] - 48;

delete[] b;

int r = la % 2, lb = (la + 1) / 2, lc;

b = new char[lb];

if (r == 1)

{

b[0] = sqrt(a[la - 1]);

a[la - 1] -= b[0] * b[0];

while (la > 0 && a[la - 1] == 0)

la--;

}

else

{

int temp = 10 * a[la - 1] + a[la - 2];

b[0] = sqrt(temp);

temp -= b[0] * b[0];

a[la - 1] = temp / 10;

a[la - 2] = temp % 10;

while (la > 0 && a[la - 1] == 0)

la--;

}

if (b[0] > 4)

{

lc = 1;

c = new char[lb + 1];

c[0] = 1;

c[1] = (b[0] * 2) % 10;

}

else

{

lc = 0;

c = new char[lb];

c[0] = b[0] * 2;

}

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

{

b[i] = 0;

lc++;

c[lc] = 1;

int jinwei, jiewei;

while (compare(a, c, la, lb, lc, i) == 1)

{

b[i]++;

jiewei = 0;

int k;

for (int j = lc; j >= 0; j--)

{

k = 2 * (lb - i - 1) + lc - j;

a[k] -= c[j] + jiewei;

if (a[k] < 0)

{

a[k] += 10;

jiewei = 1;

}

else

jiewei = 0;

}

if (jiewei == 1)

a[++k]--;

while (a[la - 1] == 0)

la--;

jinwei = 2;

k = lc;

do

{

c[k] += jinwei;

if (c[k] > 9)

{

jinwei = 1;

c[k] -= 10;

}

else

jinwei = 0;

k--;

} while (jinwei == 1);

}

c[lc]--;

}

for (int i = 0; i < lb; i++)

{

cout << (int)b[i];

}

}
未经允许不得转载!大整数开根

update

纸上得来终觉浅, 绝知此事须躬行。