[UVA] 10023 - Square root

題目連結

題意:

給你一個整數 n，求出 n 的 正平方根。
n 介於 1 到 10的1000次方。
--------------------------------------------------

我的作法:

利用二分法找根，雖然效率不好但可以過!
可以先寫 int 版本進行測試，
測試OK再將 int 改成大樹class，
重載有用到的運算子~

注意喔!題目中有一句話:
It is guaranteed, that for given Y , X will be always an integer.
的中文翻譯是
保證Y不會是一個整數的平方哦 !
所以像是 99 開方根要輸出 9

--------------------------------------------------
/* 20151023
 * hanting
 * UVa 10023 - Square root
 * C++
 */
#include <iostream>
#include <cmath>
#include <iomanip>
#include <cstring>
#include <cstdlib>
using namespace std;
#define Capacity 8//每一格存8位數
const int maxValue=1e8;//每一格最大儲存值
const int Size = 255;// 1000位數*2/每一格存8位數

class BigInteger
{
private:
    long long value[Size];
    int digit;
    void digitCheck();
    void Carry();
    void init();
public:
    BigInteger():digit(0)
    {
        memset(value, 0 ,sizeof(value));
    }
    friend istream& operator>>(istream& in,BigInteger &B);
    friend ostream& operator<<(ostream& out,BigInteger &B);
    void operator = (int n);
    bool operator < (BigInteger &B);
    bool operator > (BigInteger &B);
    BigInteger operator + (int n);
    BigInteger operator + (BigInteger &B);
    BigInteger operator * (BigInteger &B);
    BigInteger operator / (int n);
    void operator--(int t);
};
BigInteger SquareRoot(BigInteger &num)
{
    BigInteger low, up, mid;
    low = 1;
    up = num;
    mid = (low + up) / 2;
    while(low < up)
    {
        if(mid * mid > num)
        {
            up = mid;
            mid = (low + up) / 2;
        }
        else if(mid * mid < num)
        {
            low = mid + 1;
            mid = (low + up) / 2;
        }
        else
        {
            return mid;
        }
    }
}
int main()
{
    int testCase;
    cin>>testCase;
    while(testCase--)
    {
        BigInteger num;
        cin >> num;
        BigInteger ans = SquareRoot(num);
        if(ans*ans > num)//99開根號是9
        {
            ans--;
        }
        cout << ans << endl;
        if(testCase) cout<<endl;
    }
    return 0;
}
void BigInteger::init()
{
    memset(value , 0 ,sizeof(value));
    digit=0;
}
istream& operator>>(istream& in,BigInteger &B)
{
    B.init();
    string str;
    in >> str;
    while( str.size() >= Capacity )
    {
        B.value[B.digit++] = atoi((char*)(str.substr(str.size()-Capacity)).c_str());
        str.erase(str.size()-Capacity,Capacity);
    }
    if(str.size())
    {
        B.value[B.digit++] = atoi((char*)str.c_str());
    }
    return in;
}

ostream& operator<<(ostream& out,BigInteger &B)
{
    out << B.value[B.digit-1] ;
    for(int i = B.digit-2; i >= 0;i--)
    {
        out << setw(Capacity) << setfill('0') << B.value[i] ;
    }
    return out;
}
void BigInteger::digitCheck()
{
    while(!value[digit-1]) digit--;
}
void BigInteger::Carry()
{
    for(int i = 0; i < digit ; i++)
    {
        value[i+1] += value[i]/maxValue;
        value[i] %= maxValue;
    }
}
void BigInteger::operator = (int n)
{
    value[0] = n;
    digit = 1;
    /*Carry();
    digitCheck();*/
}
bool BigInteger::operator < (BigInteger &B)
{
    if(digit > B.digit) return false;
    else if (digit < B.digit) return true;
    else//digit == B.digit
    {
        for(int i = digit-1; i >= 0; i--)
        {
            if(value[i] > B.value[i]) return false;
            else if(value[i] < B.value[i]) return true;
        }
    }
    return false;
}
bool BigInteger::operator > (BigInteger &B)
{
    if(digit > B.digit) return true;
    else if (digit < B.digit) return false;
    else//digit == B.digit
    {
        for(int i = digit-1; i >= 0; i--)
        {
            if(value[i] > B.value[i]) return true;
            else if(value[i] < B.value[i]) return false;
        }
    }
    return false;
}
BigInteger BigInteger::operator + (int n)
{
    BigInteger result = *this;
    result.value[0] += n;
    result.Carry();
    result.digitCheck();

    return result;
}
BigInteger BigInteger::operator + (BigInteger &B)
{
   BigInteger result;
   for(int i = 0; i < digit or i < B.digit ;i++)
   {
       result.value[i] = value[i] + B.value[i];
   }
   result.digit = max(digit, B.digit) + 1;
   result.Carry();
   result.digitCheck();
   return result;
}
BigInteger BigInteger::operator * (BigInteger &B)
{
    BigInteger result;
    for(int i = 0; i < digit ;i++)
    {
        for(int j = 0; j < B.digit ;j++)
        {
            result.value[i+j] += value[i] * B.value[j];
        }
    }
    result.digit = digit + B.digit + 1;
    result.Carry();
    result.digitCheck();

    return result;
}
BigInteger BigInteger::operator / (int n)
{
    BigInteger result = *this;
    for(int i = digit-2; i >= 0 ; i--)
    {
        result.value[i] += maxValue*(result.value[i+1]&1);
        result.value[i+1] /= 2;
    }
    result.value[0] /= 2;
    result.digitCheck();
    return result;
}
void BigInteger::operator--(int t)
{
    value[digit-1]--;
    for(int i=digit-2;i>=0;i--)
    {
        value[i]+=maxValue-1;
    }
    Carry();
    digitCheck();
}