二分做法,死活不用string,别为我为什么,问就是我也不知道.计算长度好麻烦啊

所以我为什么要写它

就是个高精度大集合,包含:

• 高精度比大小
• 高精度加法
• 高精度乘法
• 高精度除低精度

思路:

输入的大整数为$x$.

进行二分,其中$l$和$r$都是数组(因为高精,但为了方便,后面都是直接加减),while条件为$l+1<r$.

循环里面取$mid$,若$mid^2<x$,缩小范围,$l=mid$,否则$r=mid$.

最后输出$l$.

#include <iostream>
using namespace std;

int x[10001],n,l[10001],r[10001],mid[10001];
int last[10001],lsize,rsize,midsize;
int one[10001] = {0,1};
string s;
const int big = 1000;

int add(int a[],int b[],int len1,int len2)//加
{
	for(int i = 0;i <= big;i++) last[i] = 0;
	int jin = 0,m = max(len1,len2);
	for(int i = 1;i <= m;i++)
	{
		last[i] = (jin + a[i] + b[i]) % 10;
		jin = (jin + a[i] + b[i]) / 10;
	}
	last[m + 1] = jin;
	int cnt = 0;
    bool flag = true;
    for(int i = big;i >= 1;i--)
    {
    	if(last[i] == 0 && flag) continue;
    	flag = false;
    	cnt++;
	}
    return cnt;
}

bool low(int a[],int b[],int len1,int len2)//比大小,若等于返回false
{
	for(int i = max(len1,len2);i >= 1;i++)
	{
		if(a[i] > b[i]) return false;
		else if(a[i] < b[i]) return true;
	}
	return false;
}

int qur(int a[],int len1)//高精度除以2
{
	int yu = 0;
	for(int i = len1;i >= 1;i--)
    {
        mid[i] = (a[i] + yu * 10) / 2;
        yu = (a[i] + yu * 10) % 2;
    }
    int cnt = 0;
    bool flag = true;
    for(int i = big;i >= 1;i--)
    {
    	if(mid[i] == 0 && flag) continue;
    	flag = false;
    	cnt++;
	}
    return cnt;
}

int times(int a[],int len1)//乘法
{
	for(int i = 0;i <= big;i++) last[i] = 0;
	int jin;
	for(int i = 1;i <= len1;i++)
	{
		jin = 0;
		for(int j = 1;j <= len1;j++)
		{
			last[i + j] += a[i] * a[j] + jin;
			jin = last[i + j] / 10;
			last[i + j] %= 10;
		}
		last[i + len1 + 1] += jin;
	}
	for(int i = 2;i <= big;i++) swap(last[i],last[i - 1]);
	int cnt = 0;
    bool flag = true;
    for(int i = big;i >= 1;i--)
    {
    	if(last[i] == 0 && flag) continue;
    	flag = false;
    	cnt++;
	}
    return cnt;
}

bool eq(int a[],int b[],int len1,int len2)//比大小,若等于返回true
{
	for(int i = max(len1,len2);i >= 1;i--)
	{
		if(a[i] > b[i]) return false;
		else if(a[i] < b[i]) return true;
	}
	return true;
}

signed main()
{
	cin >> s;
	n = s.size();
	for(int i = n - 1;i >= 0;i--) x[n - i] = s[i] - '0';
	l[1] = 1;
	for(int i = 1;i <= n;i++) r[i] = x[i];
	lsize = 1;
	rsize = n;
	while(1)//二分
	{
//		for(int i = lsize;i >= 1;i--) cout<<l[i];
//		cout<<' ';
//		for(int i = rsize;i >= 1;i--) cout<<r[i];
//		cout<<endl;
		int cd = add(l,one,lsize,1);
		if(!low(last,r,cd,rsize)) break;
		cd = add(l,r,lsize,rsize);
		midsize = qur(last,cd);
		cd = times(mid,midsize);
		if(eq(last,x,cd,n))
		{
			for(int i = 1;i <= max(midsize,lsize);i++) l[i] = mid[i];
			lsize = midsize;
		}
		else
		{
			for(int i = 1;i <= max(midsize,rsize);i++) r[i] = mid[i];
			rsize = midsize;
		}
	}
	for(int i = lsize;i >= 1;i--) cout << l[i];
	cout << endl;
	int aa = times(l,lsize);
	for(int i = aa;i >= 1;i--) cout << last[i];
    return 0;
}

还有bug,随便一测就是bug而且很慢

我要留坑!