30分求助
查看原帖
30分求助
184055
Beyond616楼主2020/11/3 10:25
#include<cstdio>
#include<cstring>
#define ll long long
#define N 10090
class BigInt
{	
	public:
	ll num[N],len;
	bool operator >= (const BigInt &x) const 
	{
		if (num[0]!=x.num[0]) 
		return num[0]<x.num[0];
		bool fh=num[0];
		if (len!=x.len) return fh?len<x.len:len>x.len;
		for (ll i=len;i>=1;--i)
		if (num[i]!=x.num[i])
		return fh?num[i]<x.num[i]:num[i]>x.num[i];
		return true;
	}
	bool operator == (const BigInt &x) const 
	{
		if (num[0]!=x.num[0]) return 0;
		if (len!=x.len) return 0;
		for (ll i=1;i<=len;++i)
		if (num[i]!=x.num[i]) return 0;
		return 1;
	}
//	BigInt operator - (const BigInt) const;
	BigInt operator + (const BigInt &x) const
	{
		BigInt g=*this,sum;
		if (num[0]==x.num[0]) sum.num[0]=num[0];
		else {
			BigInt y=x,ans;
			bool fh,com;
			if (g.num[0]==1) fh=1;
			g.num[0]=y.num[0]=0;
			com=g>=y;
			if (com==1)
			{
				ans=g-y;
				ans.num[0]=fh;
			} else
			{
				ans=y-g;
				ans.num[0]=1-fh;
			}
			return ans;
		}
		sum.len=len>x.len?len:x.len;
		for (ll i=1;i<=sum.len;++i)
		{
			sum.num[i]+=num[i]+x.num[i];
			sum.num[i+1]=sum.num[i]/10;
			sum.num[i]%=10;
		}
		if (sum.num[sum.len+1]) ++sum.len;
		return sum;
	}
	BigInt operator + (const ll &x) const//zhengshuxia
	{
		BigInt ans=*this;
		ans.num[1]+=x;
		for (ll i=1;i<=ans.len;++i)
		{
			ans.num[i+1]+=ans.num[i]/10;
			ans.num[i]%=10;
		}
		if (ans.num[ans.len+1]) ++ans.len;
		return ans;
	}
	BigInt operator - (const ll &x) const//zhengshuxia
	{
		BigInt ans=*this;
		ans.num[1]-=x;
		ll p=1;
		while (ans.num[p]<0)
		{
			ans.num[p]+=10;
			--ans.num[++p];
		}
		while (ans.num[ans.len]==0&&ans.len!=1) --ans.len;
		if (ans.len==1&&ans.num==0) ans.num[0]=0;
		return ans;
	}
	BigInt operator - (const BigInt &x) const
	{
		BigInt g=*this,sum,y=x;sum.empty();
		if (g.num[0]!=x.num[0])
		{
			bool fh=g.num[0];
			g.num[0]=y.num[0]=0;
			sum=g+y;
			sum.num[0]=fh;
			return sum;
		}
		bool fh=g.num[0];
		g.num[0]=y.num[0]=0;
		BigInt ans;
		ans.empty();
		if (!(g>=y)) 
		{
			ans=y-g;
			ans.num[0]=1-fh;
			return ans;
		}
		if (fh==1)
		{
			ans=g-y;
			ans.num[0]=1;
			return ans;
		}
		ans.empty();
		for (ll i=1;i<=len;++i)
		{
			if (g.num[i]<x.num[i])
			{
				ans.num[i]=g.num[i]+10-x.num[i];
				--g.num[i+1];
			} else ans.num[i]=g.num[i]-x.num[i];
		}
		ans.len=g.len;
		while (ans.num[ans.len]==0&&ans.len!=1) --ans.len;
		if (ans.len==1&&ans.num==0) ans.num[0]=0;
		return ans;
	}
	void empty()
	{
		memset(num,0,sizeof(num));
		len=1;
	}
	BigInt operator * (const BigInt &x) const
	{
		BigInt res; res.empty();
		res.len=len+x.len;
		for (ll i=1;i<=len;++i)
		for (ll j=1;j<=x.len;++j)
		res.num[i+j-1]+=num[i]*x.num[j];
		for (ll i=1;i<=res.len;++i)
		{
			res.num[i+1]+=res.num[i]/10;
			res.num[i]%=10;
		}
		while (res.num[res.len]==0&&res.len!=1) --res.len;
		if (res.len==1&&res.num==0) res.num[0]=0;
		return res;
	}
	void read()
	{
		char s[N];ll l,p=0;
		scanf("%s",s);
		if (s[0]=='-') p=num[0]=1;
		l=strlen(s);
		for (ll i=1;i<=l-p;++i)
		num[i]=s[l-i]-'0'; len=l-p;
	}
	BigInt operator / (const ll &b) const
	{
		BigInt a=*this,ans;
		ans.empty();
		ll k=0;
		for (ll i=a.len;i>=1;--i)
		{
			ans.num[i]=(k*10+a.num[i])/b;
			k=(k*10+a.num[i])%b;
		}
		ans.len=a.len;
		while (ans.num[ans.len]==0&&ans.len!=1) --ans.len;
		if (ans.len==1&&ans.num==0) ans.num[0]=0;
		return ans;
	}
	ll operator % (const ll &b) const
	{
		BigInt a=*this,ans;
		ans.empty();
		ll k=0;
		for (ll i=a.len;i>=1;--i)
		{
			ans.num[i]=(k*10+a.num[i])/b;
			k=(k*10+a.num[i])%b;
		}
		return k;
	}
	BigInt Sq(ll n)
	{
		BigInt ans,x=*this;
		ans.len=ans.num[1]=1;
		while (n!=0)
		{
			if (n%2!=0) ans=ans*x;
			x=x*x;
			n/=2;
		}
		return ans;
	}
	inline void print()
	{
		if (num[0]==1) printf("-");
		for (ll i=len;i>=1;--i) printf("%lld",num[i]);
		printf("\n");
	}
}x,ans,l,r,mid;
ll m;
int main()
{
	scanf("%lld",&m);
	x.read();
	l.empty(); r=x;
	while (r>=l)
	{
		mid=(l+r)/2;
		if (mid.Sq(m)>=x&&!(mid.Sq(m)==x)) r=mid-1;
		else {
			ans=mid;
			l=mid+1;
		}
	}
	ans.print();
}

多写了亿些东西,请大家不要在意

2020/11/3 10:25
加载中...