|
试题描述
|
|
给出一个正整数n，求n开根号后的整数部分的值。n的位数不超过1000位。
|
|
输入
|
|
读入一个不超过1000位的正整数n。
|
|
输出
|
|
输出所求答案
|
|
输入示例
|
|
17
|
|
输出示例
|
|
4
|
高精度开根：需要用的是手算开平方根的方法，我其实这个方法也不会，是临时到网上学习的
网上说的方法都挺详细的，我在这里就不详细说了，下面直接贴代码：
高精度模板需要用到高减高，高乘低，高加低。
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
typedef long long LL;
inline int read()
{
int x=,f=;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-;c=getchar();}
while(isdigit(c)){x=x*+c-'';c=getchar();}
return x*f;
}
const int maxn=;
struct data
{
int l,v[maxn];
data(){l=;memset(v,,sizeof(v));}
data operator = (const data& s)
{
l=s.l;memset(v,,sizeof(v));
for(int i=;i<=l;i++)v[i]=s.v[i];
return *this;
}
data operator = (const int& s)
{
l=;v[]=s;
while(v[l]>)v[l+]+=v[l]/,v[l]%=,l++;
return *this;
}
data operator - (const data& s)
{
data c;c.l=l;
for(int i=;i<=c.l;i++)c.v[i]=v[i];
for(int i=;i<=c.l;i++)c.v[i]-=s.v[i];
for(int i=;i<c.l;i++)if(c.v[i]<)c.v[i]+=,c.v[i+]--;
while(!c.v[c.l])c.l--;
return c;
}
data operator * (const int& s)
{
data c;c.l=l;
for(int i=;i<=c.l;i++)c.v[i]=v[i]*s;
for(int i=;i<c.l;i++)if(c.v[i]>)c.v[i+]+=(c.v[i])/,c.v[i]%=;
while(c.v[c.l]>)c.v[c.l+]+=(c.v[c.l])/,c.v[c.l]%=,c.l++;
return c;
}
data operator + (const int& s)
{
data c=*this;
c.v[]+=s;int i=;
while(c.v[i]>)c.v[i+]+=c.v[i]/,c.v[i]%=,i++;
c.l=max(c.l,i);
return c;
}
bool operator <= (const data& t)const
{
if(l!=t.l)return l<t.l;
for(int i=l;i;i--)if(v[i]!=t.v[i])return v[i]<t.v[i];
return ;
}
}a;
int num[];
void scan(data &s)
{
char ch[maxn];
scanf("%s",ch+);s.l=strlen(ch+);
for(int i=;i<=s.l;i++)s.v[i]=ch[s.l-i+]-'';
return;
}
void print(data s){for(int i=s.l;i;i--)printf("%d",s.v[i]);cout<<endl;}
void init(data s)//将这个数从个位起，向左每两位分一节(例如65536变成6，55，36)
{
if(s.l%)
{
num[]=s.v[s.l];
for(int i=;i<=s.l;i+=)num[i/]=s.v[s.l-i+]*+s.v[s.l-i];
}
else for(int i=;i<=s.l;i+=)num[i/]=s.v[s.l-i+]*+s.v[s.l-i];
return;
}
data Sqrt(data s)
{
data ans,t,q,p;
ans=;t=;
int len= s.l% ? s.l/+ : s.l/;//划分块的数量
for(int i=;i<len;i++)
{
t=(t*)+num[i];
p=ans*;ans=ans*;//这里的ans要提前乘以10，如果下面的循环一次都没进去的话，ans就不会更新了
for(int j=;j>=;j--)
{
q=(p+j)*j;
if(q<=t)
{
ans=ans+j;
t=t-q;
break;
}
}
}
return ans;
}
int main()
{
scan(a);
init(a);
print(Sqrt(a));
return ;
}