一つの神仙高精度圧縮問題#
問題#
1 月 28 日の試験からの問題です。
高精度の平方根【水】#
説明#
タイトルに書かれている通りです。
入力#
整数 N が与えられます。
出力#
N の平方根の床関数を出力してください。
入力例 1#
1
出力例 1#
1
ヒント#
100% のデータに対して、0<N<=10^1000 です。
分析#
まず、タイトルに大きな「水」と書かれているので、これは簡単な問題だ、事情は簡単ではありません。
普通の高精度計算を行いましたが、各点には 1000 桁ありました。。。。
したがって、圧縮が必要ですが、最初は分かりませんでした。2 日後の今日、やっと書きました！
コード（板子）#
#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//圧縮する桁数
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;
}
なんと 200 行以上もあります。
機能は充実しています（ではないですが）、高精度 ÷ 高精度がないだけです。。。
書いた後、WA が続いて、問題が見つからないままでした。。。
結果、問題が交差していたことがわかりました（顔を隠す）
