503 lines
10 KiB
C++
503 lines
10 KiB
C++
#include "lint.hpp"
|
||
|
||
void get(vector< complex<long double> > x)
|
||
{
|
||
for(uint i = x.size() - 1; i >= 0; i--) {
|
||
if(i > x.size()) break;
|
||
cout << x[i] << " ";
|
||
}
|
||
cout << endl << endl;
|
||
}
|
||
|
||
void get(vuint x)
|
||
{
|
||
for(uint i = x.size() - 1; i >= 0; i--) {
|
||
if(i > x.size()) break;
|
||
cout << x[i] << " ";
|
||
}
|
||
cout << endl << endl;
|
||
}
|
||
|
||
|
||
lint::lint() { }
|
||
|
||
lint::lint(string lintin)
|
||
{
|
||
operator =(lintin);
|
||
}
|
||
|
||
lint::~lint()
|
||
{ num.clear(); }
|
||
|
||
void lint::operator =(string strin)
|
||
{
|
||
sign = 1;
|
||
strin = del(strin);
|
||
if(strin[0] == '-') {
|
||
sign = -1;
|
||
strin = strin.substr(1, strin.size() - 1);
|
||
}
|
||
|
||
/* 整理输入，使其全是数字，并且首位无0 */
|
||
for(uint i = 0; i < strin.size(); i++)
|
||
if(strin[i] > '9' || strin[i] < '0') strin[i] = '0';
|
||
|
||
length = strin.size();
|
||
len = (length + unit - 1) / unit;
|
||
uint mod = length % unit;
|
||
if(num.capacity()) num.clear();
|
||
num.resize(len);
|
||
|
||
for(uint i = 0; i < len - 1; i++)
|
||
num[i] = atoi(strin.substr(length - (i + 1) * unit, unit).c_str());
|
||
num[len - 1] = atoi(strin.substr(0, (mod == 0) ? unit : mod).c_str());
|
||
}
|
||
|
||
|
||
/* 提取十进制数值 */
|
||
string lint::getd()
|
||
{ return vtos(num); }
|
||
|
||
vuint lint::getvec()
|
||
{
|
||
return num;
|
||
}
|
||
|
||
/* 提取 vector 中相应位置的数字 */
|
||
uint lint::operator [](uint locale)
|
||
{
|
||
if(locale >= len) return 0;
|
||
else return num[locale];
|
||
}
|
||
|
||
/* 提取 vector 的长度 */
|
||
uint lint::getlen()
|
||
{ return len; }
|
||
|
||
/* 提取整数长度 */
|
||
uint lint::getlength()
|
||
{ return length; }
|
||
|
||
int lint::getsign()
|
||
{ return sign; }
|
||
|
||
|
||
/* 定义加法 */
|
||
string lint::operator +(lint opnum)
|
||
{
|
||
if(sign * opnum.getsign() == -1) {
|
||
if(sign == -1) {
|
||
lint abs(getd());
|
||
return opnum - abs;
|
||
} else {
|
||
lint abs(opnum.getd());
|
||
lint absa(getd());
|
||
return absa - abs;
|
||
}
|
||
} else {
|
||
vuint sumint(1);
|
||
vuint sumshort(1);
|
||
|
||
if(len >= opnum.getlen()) {
|
||
sumint.resize(len);
|
||
sumint = getvec();
|
||
sumshort = opnum.getvec();
|
||
} else {
|
||
sumint.resize(opnum.getlen());
|
||
sumint = opnum.getvec();
|
||
sumshort = getvec();
|
||
}
|
||
|
||
sumint.resize(sumint.size() + 1);
|
||
sumint[sumint.size()] = 0;
|
||
|
||
uint temp;
|
||
|
||
for(uint i = 0; i < sumshort.size(); i++) {
|
||
temp = sumint[i] + sumshort[i];
|
||
sumint[i] = temp % cunit;
|
||
sumint[i + 1] += temp / cunit;
|
||
}
|
||
for(uint i = sumshort.size(); i < sumint.size() - 1; i++) {
|
||
temp = sumint[i];
|
||
sumint[i] = temp % cunit;
|
||
sumint[i + 1] += temp / cunit;
|
||
}
|
||
|
||
if(sign == -1) return "-" + vtos(sumint);
|
||
else return vtos(sumint);
|
||
}
|
||
}
|
||
|
||
string lint::operator -(lint opnum)
|
||
{
|
||
if(sign * opnum.getsign() == -1) {
|
||
if(sign == 1) return operator +(opnum);
|
||
else return "-" + operator +(opnum);
|
||
} else {
|
||
vuint difint(len >= opnum.getlen() ? len : opnum.getlen());
|
||
vuint small(len >= opnum.getlen() ? opnum.getlen() : len);
|
||
|
||
if(compare(opnum) >= 0) {
|
||
difint = num;
|
||
small = opnum.getvec();
|
||
} else {
|
||
difint = opnum.getvec();
|
||
small = num;
|
||
}
|
||
|
||
for(uint i = small.size() - 1; i >= 0; i--) {
|
||
if(i > small.size()) break;
|
||
if(difint[i] < small[i]) {
|
||
uint temp = i + 1;
|
||
while(difint[temp] == 0) {
|
||
difint[temp] = cunit - 1;
|
||
temp++;
|
||
if(temp >= difint.size()) break;
|
||
}
|
||
if(temp < difint.size()) difint[temp]--;
|
||
difint[i] += cunit;
|
||
}
|
||
difint[i] -= small[i];
|
||
}
|
||
|
||
if(sign * compare(opnum) == 1) return vtos(difint);
|
||
else return "-" + vtos(difint);
|
||
}
|
||
}
|
||
|
||
/* 定义乘法，用 FFT 实现 */
|
||
string lint::operator *(lint opnum)
|
||
{
|
||
uint a_size = len, b_size = opnum.getlen();
|
||
vector< complex<long double> > a(a_size), b(b_size);
|
||
|
||
for(uint i = 0; i < a_size; i++) a[i].real() = num[i];
|
||
for(uint i = 0; i < b_size; i++) b[i].real() = (opnum[i]);
|
||
|
||
uint n;
|
||
a_size += b_size;
|
||
for (n = a_size; n != (n&-n); n += (n&-n));
|
||
|
||
a.resize(n);
|
||
b.resize(n);
|
||
|
||
FFT(a, n);
|
||
FFT(b, n);
|
||
for (uint i = 0; i < n; i++)
|
||
a[i] *= b[i];
|
||
IFFT(a, n);
|
||
|
||
for (uint i = 0; i < a_size-1; i++) {
|
||
a[i + 1] += a[i].real() / 1000.;
|
||
a[i] = fmodl(a[i].real(), 1000.L);
|
||
a[i].real() += eps;
|
||
}
|
||
|
||
vuint mulout(n);
|
||
for(uint i = 0; i < a.size(); i++) mulout[i] = a[i].real();
|
||
|
||
if(sign * opnum.getsign() == -1) return "-" + vtos(mulout);
|
||
else return vtos(mulout);
|
||
}
|
||
|
||
int lint::operator ==(lint opnum)
|
||
{
|
||
if(sign * opnum.getsign() > 0) {
|
||
if(sign == 1) return compare(opnum);
|
||
if(sign == -1) return -(compare(opnum));
|
||
else return 0;
|
||
} else {
|
||
if(sign == 1) return 1;
|
||
else return -1;
|
||
}
|
||
}
|
||
|
||
int lint::compare(lint opnum)
|
||
{
|
||
if(length > opnum.getlength()) return 1;
|
||
if(length < opnum.getlength()) return -1;
|
||
else {
|
||
for(uint i = len - 1; i >= 0; i--) {
|
||
if(i > len - 1) break;
|
||
if(num[i] > (opnum[i])) return 1;
|
||
if(num[i] < (opnum[i])) return -1;
|
||
}
|
||
return 0;
|
||
}
|
||
}
|
||
|
||
/* 定义除法 */
|
||
string lint::operator /(lint opnum)
|
||
{
|
||
if(compare(opnum) == -1) return "0";
|
||
if(compare(opnum) == 0) return "1";
|
||
else {
|
||
uint move = len - opnum.getlen();
|
||
vuint devint(move + 1);
|
||
vuint open = getvec();
|
||
open.resize(len + 1);
|
||
open[len] = 0;
|
||
for(uint i = move; i >= 0; i--) {
|
||
if(i > move) break;
|
||
uint high = i + opnum.getlen() - 1;
|
||
if(open.capacity() <= high) {
|
||
open.resize(high + 2);
|
||
open[high + 1] = 0;
|
||
}
|
||
uint temp = (open[high] + open[high + 1] * cunit) / opnum.getvec().back() + 2;
|
||
vuint tryvec;
|
||
int count = 1;
|
||
do {
|
||
if(--temp > cunit * cunit) temp = 1;
|
||
tryvec = vmul(opnum.getvec(), temp, i);
|
||
count++;
|
||
} while(vless(open, tryvec) && count < 20);
|
||
devint[i] = temp;
|
||
open = vdif(open, tryvec);
|
||
open[open.size()] = 0;
|
||
tryvec.clear();
|
||
}
|
||
if(sign * opnum.getsign() == 1) return vtos(devint);
|
||
else return "-" + vtos(devint);
|
||
}
|
||
}
|
||
|
||
|
||
string lint::operator %(lint opnum)
|
||
{
|
||
if(sign == 1 && compare(opnum) == -1) return getd();
|
||
else {
|
||
lint div = getd();
|
||
lint q = (div / opnum);
|
||
lint mod = (div - (q * opnum));
|
||
if(sign == 1) return mod.getd();
|
||
else return (opnum - mod);
|
||
}
|
||
}
|
||
|
||
vuint lint::getbit()
|
||
{
|
||
vuint out(len * 3);
|
||
lint opnum = getd();
|
||
lint bit("2");
|
||
uint i;
|
||
for(i = 0; i < len * 3; i++) {
|
||
if(opnum % bit == "1") out[i] = 1;
|
||
else out[i] = 0;
|
||
opnum = opnum / bit;
|
||
}
|
||
while(opnum.getd() != "0") {
|
||
out.resize(i + 2);
|
||
if(opnum % bit == "1") out[i] = 1;
|
||
else out[i] = 0;
|
||
opnum = opnum / bit;
|
||
i++;
|
||
}
|
||
return del(out);
|
||
}
|
||
|
||
|
||
string lint::operator ^(lint opnum)
|
||
{
|
||
lint power("1");
|
||
lint base = getd();
|
||
for(uint i = opnum.getbit().size() - 1; i >= 0; i--) {
|
||
if(i > opnum.getbit().size()) break;
|
||
power = (power * power);
|
||
if(opnum.getbit()[i] == 1) power = (power * base);
|
||
}
|
||
|
||
return del(power.getd());
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
/* 消去首位0 */
|
||
string del(string undel)
|
||
{
|
||
uint flag = 0;
|
||
while(undel.substr(0, 2) == "--") undel = undel.substr(2, undel.size() - 2);
|
||
if(undel[0] == '-') {
|
||
undel = undel.substr(1, undel.size() - 1);
|
||
flag = 1;
|
||
}
|
||
while(undel.size() > 1 && undel[0] == '0')
|
||
undel = undel.substr(1, undel.size() - 1);
|
||
if(undel.size() == 1 && undel[0] == '0') return "0";
|
||
if(flag) return "-" + undel;
|
||
return undel;
|
||
}
|
||
|
||
vuint del(vuint undel)
|
||
{
|
||
while(undel[undel.size() - 1] == 0) undel.pop_back();
|
||
vuint out(undel.size());
|
||
for(uint i = 0; i < undel.size(); i++) out[i] = undel[i];
|
||
return out;
|
||
}
|
||
|
||
|
||
/* 整数到字符串的转换 */
|
||
string itos(uint intin)
|
||
{
|
||
string strout = "";
|
||
if(intin == 0) return "0";
|
||
while(intin > 0) {
|
||
char temp = intin % carry + '0';
|
||
strout = temp + strout;
|
||
intin /= carry;
|
||
}
|
||
return strout;
|
||
}
|
||
|
||
|
||
/* 向量到字符串的转换 */
|
||
string vtos(vuint vin)
|
||
{
|
||
string strout = "";
|
||
string temp = "";
|
||
for(uint i = vin.size() - 1; i >= 0; i--) {
|
||
if(i > vin.size() - 1) break;
|
||
temp = itos(vin[i] % cunit);
|
||
while(temp.size() < unit) temp = "0" + temp;
|
||
strout += temp;
|
||
}
|
||
|
||
return del(strout);
|
||
}
|
||
/**
|
||
向量转比特流
|
||
string vtobit(vuint vin)
|
||
{
|
||
string strout = "";
|
||
for(uint i = vin.size() - 1; i >= 0; i--) {
|
||
if(i > vin.size()) break;
|
||
if(vin[i]) strout += "1";
|
||
else strout += "0";
|
||
}
|
||
return del(strout);
|
||
}*/
|
||
|
||
/* 向量和整数的乘法 */
|
||
vuint vmul(vuint op, uint opnum, uint power = 0)
|
||
{
|
||
if(power) {
|
||
op.resize(op.size() + power);
|
||
for(uint i = op.size() - 1; i >= power; i--) {
|
||
if(i > op.size()) break;
|
||
op[i] = op[i - power];
|
||
}
|
||
for(uint i = power - 1; i >= 0; i--) {
|
||
if(i > op.size()) break;
|
||
op[i] = 0;
|
||
}
|
||
}
|
||
lint big(vtos(op));
|
||
lint small(itos(opnum));
|
||
lint out(big * small);
|
||
return out.getvec();
|
||
}
|
||
|
||
|
||
/* 向量减法 */
|
||
vuint vdif(vuint big, vuint small)
|
||
{
|
||
lint bigint(vtos(big));
|
||
lint smallint(vtos(small));
|
||
if(bigint.compare(smallint) == -1) return big;
|
||
else {
|
||
lint out(bigint - smallint);
|
||
return out.getvec();
|
||
}
|
||
}
|
||
|
||
/* 比较大小 */
|
||
uint vless(vuint big, vuint small)
|
||
{
|
||
lint bigint(vtos(big));
|
||
lint smallint(vtos(small));
|
||
if(bigint.compare(smallint) == -1) return 1;
|
||
else return 0;
|
||
}
|
||
|
||
/* 快速傅立叶变换 */
|
||
void FFT(vector< complex<long double> > &x, uint n)
|
||
{
|
||
uint i,j,k,t;
|
||
|
||
for (i = 0; i < n; ++i) {
|
||
j = 0;
|
||
for (t = i, k = n; k /= 2; t /= 2)
|
||
j = j*2+t%2;
|
||
if (j > i) swap(x[j], x[i]);
|
||
}
|
||
|
||
for (k = 2; k <= n; k *= 2) {
|
||
const complex<long double> omega_unit(cosl(2*PI/k), sinl(2*PI/k));
|
||
for (i = 0; i < n; i += k) {
|
||
complex<long double> omega(1, 0);
|
||
for (j = 0; j < k/2; ++j) {
|
||
complex<long double> t = omega*x[i+j+k/2];
|
||
x[i+j+k/2] = x[i+j]-t;
|
||
x[i+j] += t;
|
||
omega *= omega_unit;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
void IFFT(vector< complex<long double> > &x, uint n)
|
||
{ uint i,j,k,t;
|
||
for (i = 0; i < n; ++i) {
|
||
j = 0;
|
||
for (t = i, k = n; k /= 2; t /= 2)
|
||
j = j*2+t%2;
|
||
if (j > i) swap(x[j], x[i]);
|
||
}
|
||
for (k = 2; k <= n; k *= 2) {
|
||
const complex<long double> omega_unit(cosl(-2*PI/k), sinl(-2*PI/k));
|
||
for (i = 0; i < n; i += k) {
|
||
complex<long double> omega(1, 0);
|
||
for (j = 0; j < k/2; ++j) {
|
||
complex<long double> t = omega*x[i+j+k/2];
|
||
x[i+j+k/2] = x[i+j]-t;
|
||
x[i+j] += t;
|
||
omega *= omega_unit;
|
||
}
|
||
}
|
||
}
|
||
for (i = 0; i < n; ++i)
|
||
x[i] /= n;
|
||
}
|
||
|
||
|
||
/* 求两数最大公约数 */
|
||
string gcd(lint a, lint b)
|
||
{
|
||
if(b.getd() == "0") return a.getd();
|
||
else {
|
||
lint newb = a % b;
|
||
return gcd(b, newb);
|
||
}
|
||
}
|