題意:
給你一個整數 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();
}
