一道神仙高精度壓位板子題#
題目#
出自 1.28 的考試
高精度開平方【水】#
描述#
如題目所屬
輸入#
一個整數 N。
輸出#
N 的平方根下取整。
輸入範例 1#
1
輸出範例 1#
1
提示#
對於 100% 的數據，0<N<=10^1000。
分析#
首先看標題裡的一個大大的水我就知道這是一道水題事情不簡單
慢速打了一個普通的高精度。
後來發現每個點都有 1000 位。。。。
所以需要壓位，當然，開始我是不會的。兩天後的今天我終於寫了出來！
代碼（板子）#
#include<bits/stdc++.h>
#define LL long long
#define max(a,b) ((a)>(b))?(a):(b)
#define min(a,b) ((a)<(b))?(a):(b)
#define p 8//要壓的位數
#define carry 100000000//相應的10的P次方 用於進位
using namespace std;
const LL MAXN=3005;
const string scarry="100000000";
struct bigNum{
private:
LL t[MAXN],siz;
public:
bigNum(string s){
memset(t,0,sizeof(t));
siz=0;
LL len=s.size();
string tmp;
tmp.resize(p);
while(len>=p){
for(LL i=0;i<p;++i){
tmp[i]=s[len-p+i];
}
++siz;
for(LL i=0;i<tmp.size();++i){
t[siz]+=tmp[i]-'0';
if(i<tmp.size()-1){
t[siz]*=10;
}
}
len-=p;
}
if(len){
tmp="";
tmp.resize(len);
for(LL i=0;i<len;++i){
tmp[i]=s[i];
}
++siz;
for(LL i=0;i<tmp.size();++i){
t[siz]+=tmp[i]-'0';
if(i<tmp.size()-1){
t[siz]*=10;
}
}
}
}
bigNum(void){
memset(t,0,sizeof(t));
siz=1;
return;
}
bigNum(LL x){
memset(t,0,sizeof(t));
char tmp[3005];
siz=0;
while(x){
tmp[++siz]=x%10+'0';
x/=10;
}
*this=(string)tmp;
return;
}
void print(void){
printf("%d",t[siz]);
for(LL i=siz-1;i>=1;--i){
char tmp[]="%00d";
tmp[2]=p+'0';
printf(tmp,t[i]);
}
putchar('\n');
}
LL size(void){
return siz;
}
friend bigNum operator -(bigNum a,bigNum b){
if(a==b)return (bigNum)0;
if(a<b)swap(a,b);
bigNum c;
LL jw=0;
LL len=max(a.size(),b.size());
for(LL i=1;i<=len;++i){
c.t[i]=a.t[i]-b.t[i]-jw;
if(c.t[i]<0){
jw=1;
c.t[i]+=carry;
}
else jw=0;
}
while(c.t[len]==0){
--len;
}
c.siz=len;
return c;
}
friend bigNum operator +(bigNum a,bigNum b){
bigNum c;
LL jw=0;
LL len=max(a.size(),b.size());
for(LL i=1;i<=len;++i){
c.t[i]=a.t[i]+b.t[i]+jw;
if(c.t[i]>=carry){
jw=1;
c.t[i]-=carry;
}
else jw=0;
}
if(jw){
c.t[++len]=1;
}
c.siz=len;
return c;
}
friend bigNum operator*(bigNum a,bigNum b){
bigNum c;
LL len=a.siz+b.siz;
for(LL i=1;i<=a.siz;i++){
for(LL j=1;j<=b.siz;j++){
c.t[i+j-1]+=a.t[i]*b.t[j];
c.t[i+j]+=c.t[i+j-1]/carry;
c.t[i+j-1]%=carry;
}
}
while(len>0 && c.t[len]==0)len--;
c.siz=len;
return c;
}
friend bigNum operator/(bigNum a,int b)
{
bigNum c;
LL g=0;
for(int i=a.siz;i>0;--i){
g=g*carry+a.t[i];
c.t[i]=g/b;
g%=b;
}
c.siz=a.siz;
while(c.siz>1&&c.t[c.siz]==0)c.siz--;
return c;
}
friend bool operator ==(bigNum a,bigNum b){
if(a.siz!=b.siz){
return 0;
}
for(LL i=1;i<=a.siz;++i){
if(a.t[i]!=b.t[i]){
return 0;
}
}
return 1;
}
friend bool operator <(bigNum a,bigNum b){
if(a.siz!=b.siz){
return a.siz<b.siz;
}
for(LL i=a.siz;i>=1;--i){
if(a.t[i]<b.t[i]){
return 1;
}
if(a.t[i]>b.t[i]){
return 0;
}
}
return 0;
}
friend bool operator <=(bigNum a,bigNum b){
return !(a>b);
}
friend bool operator >(bigNum a,bigNum b){
if(a.siz!=b.siz){
return a.size()>b.size();
}
for(LL i=a.size();i>=1;--i){
if(a.t[i]>b.t[i]){
return 1;
}
if(a.t[i]<b.t[i]){
return 0;
}
}
return 0;
}
friend bool operator >=(bigNum a,bigNum b){
return !(a<b);
}
};
int main(void){
string s;
cin>>s;
bigNum n(s);
bigNum l(1),r=n,mid,ans,yi("1");
while(l<=r){
mid=(l+r)/2;
if((mid*mid)>n){
r=mid-yi;
}
else{
ans=mid;
l=mid+yi;
}
}
ans.print();
return 0;
}
居然有兩百多行。
功能全面（bushi），除了沒有高精度 ÷ 高精度。。。
寫出來之後一直 WA，對拍都拍不出問題。。。
結果發現是交錯題了（捂臉）
