[NOIP 2011]大整数開方-解題報告

[NOIP 2011]大整数開方
★入力ファイル:hugeint.in出力ファイル:hugeint.out単純比較時間制限:1 sメモリ制限:128 MB
説明
正の整数N(1≦N≦10100)を入力し、その平方根の整数部分を二分法で計算してみます.
入力フォーマット
大きな整数N.26705
出力フォーマットOutput Format
Nの平方根の整数部分を表す数.163
テーマ分析
高精度ベースの二分

#include
#include
#include
#include
using namespace std;

struct Bign{
    static const int N = 1000,M = 1;
    static const int powm = 10;// powm = pow(10,M);
    int a[N];
    // bool_type;
    bool operator < (const Bign &num) const {
        if(a[0] != num.a[0])return a[0] < num.a[0];
        const int *b = num.a;
        int th = a[0];
        while(a[th] == b[th] && th > 0) th--;
        return a[th] < b[th];
    }
    bool operator > (const Bign &num) const {return num < *this;}
    bool operator <= (const Bign &num) const {return !(num < *this);}
    bool operator >= (const Bign &num) const {return !(num > *this);}
    bool operator != (const Bign &num) const {return num < *this  || num > *this;}
    bool operator == (const Bign &num) const {return !(num != *this);}
    // =_type;
    Bign operator = (int num){
        memset(a,0,sizeof(a));
        while(num){
            a[++a[0]] = num % powm;
            num /= powm;
        }
        return *this;
    }
    Bign (int num = 0){*this = num;}
    // +_type;
    Bign operator + (const Bign &num) const {
        Bign ret = 1;
        const int *b = num.a;
        int *c = ret.a, buf = 0;
        for(int &i = c[0]; i <= max(a[0], b[0]) || buf; i++){
            c[i] = a[i] + b[i] + buf;
            buf = c[i] / powm;
            c[i] %= powm;
        }c[0]--;
        return ret;
    }Bign operator += (const Bign &num) const {return *this + num;}

    Bign operator + (const int num) const {
        Bign ret = num;
        return *this + ret;
    }Bign operator += (const int num) const {return *this + num;}
    // -_type;
    Bign operator - (const Bign &num) const {
        if(a < num.a) return num - *this;
        Bign ret = 1;
        const int *b = num.a;
        int *c = ret.a, buf = 0; 
        for(int &i = c[0]; i < a[0] || a[i] + buf; i++){
            c[i] = a[i] + powm - b[i] + buf;
            buf = c[i] / powm - 1;
            c[i] %= powm;
        }
        while((!c[c[0]])&&c[0]>0)c[0]--;
        return ret;
    }Bign operator -= (const Bign &num) const {return *this - num;}

    Bign operator - (const int num) const {
        Bign ret = num;
        return *this - ret;
    }Bign operator -= (const int num) const {return *this - num;}
    // *_type;
    Bign operator * (const Bign &num) const {
        Bign ret;
        const int *b = num.a;
        int *c = ret.a;
        for(int i = 1; i <= b[0]; i++){
            int buf = 0;
            for(int j = 1; j <= a[0] || buf; j++){
                c[i+j-1] += a[j] * b[i] + buf;
                buf = c[i+j-1] / powm;
                c[i+j-1] %= powm;
            }
        }c[0] = a[0] + b[0];
        if(!c[c[0]]) c[0]--;
        return ret;
    }Bign operator *= (const Bign &num) const {return *this * num;}

    Bign operator * (const int num) const {
        Bign ret = num;
        return *this * ret;
    }Bign operator *= (const int num) const {return *this * num;}
    // /_type;
    Bign operator / (const int num) const {
        Bign ret = 1;
        int *c = ret.a, buf = 0;
        for(int i = a[0]; i > 0; i--){
            buf = buf * powm + a[i];
            c[i] = buf / num;
            buf %= num;
        }c[0] = a[0];
        for(int &i = c[0]; !c[i]; i--);
//      c[0]++;
        buf = 0;
        for(int i = 1; i <= c[0] || buf; i++){
            c[i] += buf;
            buf = c[i] / powm;
        }
        return ret;
    }Bign operator /= (const int num) const {return *this - num;}
    // sqrt;
    friend Bign sqrt (const Bign&);
    // io;
    void in () {
        *this = 0;
        a[0] = 1;
//      int *a = this -> a;
        char buf;
        bool brea=0;
        for(int &i = a[0]; !brea; i++){
            for(int j = 1; j <= M; j++){
                buf = getchar();
                if(buf < '0' || buf > '9')
                    {brea = 1; break;}
                a[i] += (buf - '0') * pow(10, j - 1);
            }
        }a[0]-=2;
        int l=1,r=a[0];
        while(lint buf=a[l];
            a[l]=a[r];
            a[r]=buf;
            l++; r--;
        }
    }
    void out () {
        int *a = this -> a;
        for(int i = a[0]; i > 0; i--)
            printf("%d", a[i]);
        if(a[0]==0)putchar('0');
    }
};

Bign sqrt (const Bign &num){
    Bign l = 1, r = num;
    Bign mid, buf;
    while(l < r){
        mid = (r + l) / 2;
        buf = mid * mid;
        if(buf == num) break;
        if(buf >= num) r = mid;
        else l = mid + 1;
    }l=l-1;
    return l;
//  return l * l > num? l-1: l;
}

int main(){
    freopen("hugeint.in","r",stdin);
    freopen("hugeint.out","w",stdout);
    Bign a;
    a.in();
//  a.out();
//  putchar('
');
    a=sqrt(a);
    a.out();
//  while(1);
    return 0;
}