ACM模版
普通大数运算
const int MAXSIZE = 200;
void Add(char *str1, char *str2, char *str3);
void Minus(char *str1, char *str2, char *str3);
void Mul(char *str1, char *str2, char *str3);
void Div(char *str1, char *str2, char *str3);
int main()
{
char str1[MAXSIZE], str2[MAXSIZE], str3[MAXSIZE];
while (scanf("%s %s", str1, str2) == 2)
{
if (strcmp(str1, "0"))
{
memset(str3, '0', sizeof(str3));
Add(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Minus(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Mul(str1, str2, str3);
printf("%s\n", str3);
memset(str3, '0', sizeof(str3));
Div(str1, str2, str3);
printf("%s\n", str3);
}
else
{
if (strcmp(str2, "0"))
{
printf("%s\n-%s\n0\n0\n", str2, str2);
}
else
{
printf("0\n0\n0\n0\n");
}
}
}
return 0;
}
void Add(char *str1, char *str2, char *str3)
{ // str3 = str1 + str2;
int i, j, i1, i2, tmp, carry;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
i1 = len1 - 1;
i2 = len2 - 1;
j = carry = 0;
for (; i1 >= 0 && i2 >= 0; ++j, --i1, --i2)
{
tmp = str1[i1] - '0' + str2[i2] - '0' + carry;
carry = tmp / 10;
str3[j] = tmp % 10 + '0';
}
while (i1 >= 0)
{
tmp = str1[i1--] - '0' + carry;
carry = tmp / 10;
str3[j++] = tmp % 10 + '0';
}
while (i2 >= 0)
{
tmp = str2[i2--] - '0' + carry;
carry = tmp / 10;
str3[j++] = tmp % 10 + '0';
}
if (carry)
{
str3[j++] = carry + '0';
}
str3[j] = '\0';
for (i = 0, --j; i < j; ++i, --j)
{
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Minus(char *str1, char *str2, char *str3)
{ // str3 = str1-str2 (str1 > str2)
int i, j, i1, i2, tmp, carry;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
i1 = len1 - 1;
i2 = len2 - 1;
j = carry = 0;
while (i2 >= 0)
{
tmp = str1[i1] - str2[i2] - carry;
if (tmp < 0)
{
str3[j] = tmp + 10 + '0';
carry = 1;
}
else
{
str3[j] = tmp + '0';
carry = 0;
}
i1--;
i2--;
j++;
}
while (i1 >= 0)
{
tmp = str1[i1] - '0' - carry;
if (tmp < 0)
{
str3[j] = tmp + 10 + '0';
carry = 1;
}
else
{
str3[j] = tmp + '0';
carry = 0;
}
--i1;
++j;
}
--j;
while (str3[j] == '0' && j > 0)
{
--j;
}
str3[++j] = '\0';
for (i = 0, --j; i < j; ++i, --j)
{
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Mul(char *str1, char *str2, char *str3)
{
int i, j = 0, i1, i2, tmp, carry, jj;
int len1 = (int)strlen(str1), len2 = (int)strlen(str2);
char ch;
jj = carry = 0;
for (i1 = len1 - 1; i1 >= 0; --i1)
{
j = jj;
for (i2 = len2 - 1; i2 >= 0; --i2, ++j)
{
tmp = (str3[j] - '0') + (str1[i1] - '0') * (str2[i2] - '0') + carry;
if (tmp > 9)
{
carry = tmp / 10;
str3[j] = tmp % 10 + '0';
}
else
{
str3[j] = tmp + '0';
carry = 0;
}
}
if (carry)
{
str3[j] = carry + '0';
carry = 0;
j++;
}
jj++;
}
j--;
while (str3[j] == '0' && j > 0)
{
j--;
}
str3[++j] = '\0';
for (i = 0, --j; i < j; ++i, --j)
{
ch = str3[i];
str3[i] = str3[j];
str3[j] = ch;
}
return ;
}
void Div(char *str1, char *str2, char *str3)
{
int i1, i2, i, j, jj = 0, tag, carry, cf, c[MAXSIZE];
int len1 = (int)strlen(str1), len2 = (int)strlen(str2), lend;
char d[MAXSIZE];
memset(c, 0, sizeof(c));
memcpy(d, str1, len2);
lend = len2;
j = 0;
for (i1 = len2 - 1; i1 < len1; ++i1)
{
if (lend < len2)
{
d[lend] = str1[i1+1];
c[j] = 0;
++j;
++lend;
}
else if (lend == len2)
{
jj = 1;
for (i = 0; i < lend; ++i)
{
if (d[i] > str2[i])
{
break;
}
else if (d[i] < str2[i])
{
jj = 0;
break;
}
}
if (jj == 0)
{
d[lend] = str1[i1+1];
c[j] = 0;
++j;
++lend;
continue;
}
}
if (jj == 1 || lend > len2)
{
cf = jj = 0;
while (d[jj] <= '0' && jj < lend)
{
++jj;
}
if (lend - jj > len2)
{
cf = 1;
}
else if (lend - jj < len2)
{
cf = 0;
}
else
{
i2 = 0;
cf = 1;
for (i = jj; i < lend; ++i)
{
if (d[i] < str2[i2])
{
cf = 0;
break;
}
else if (d[i] > str2[i2])
{
break;
}
++i2;
}
}
while (cf)
{
i2 = len2 - 1;
cf = 0;
for (i = lend - 1; i >= lend - len2; --i)
{
d[i] = d[i] - str2[i2] + '0';
if (d[i] < '0')
{
d[i] = d[i] + 10;
carry = 1;
--d[i - 1];
}
else
{
carry = 0;
}
--i2;
}
++c[j];
jj = 0;
while (d[jj] <= '0' && jj < lend)
{
++jj;
}
if (lend - jj > len2)
{
cf = 1;
}
else if (lend - jj < len2)
{
cf = 0;
}
else
{
i2 = 0;
cf = 1;
for (i = jj; i < lend; ++i)
{
if (d[i] < str2[i2])
{
cf = 0;
break;
}
else if (d[i] > str2[i2])
{
break;
}
++i2;
}
}
}
jj = 0;
while (d[jj] <= '0' && jj < lend)
{
++jj;
}
for (i = 0; i < lend - jj; ++i)
{
d[i] = d[i + jj];
}
d[i] = str1[i1 + 1];
lend = i + 1;
j++;
}
}
i = tag = 0;
while (c[i] == 0)
{
++i;
}
for (; i < j; ++i, ++tag)
{
str3[tag] = c[i]+'0';
}
str3[tag] = '\0';
return ;
}高效大数运算
/*
* < , <= , + , - , * , / , %(修改/的最后一行可得)
*/
const int base = 10000; // (base^2) fit into int
const int width = 4; // width = log_10(base)
const int MAXN = 100000; // MAXN * width: 可表示的最大位数
const int MAXC = 1e5 + 10;
struct bint
{
int ln, v[MAXN];
bint (int r = 0)
{
// r应该是字符串!
for (ln = 0; r > 0; r /= base)
{
v[ln++] = r % base;
}
}
bint &operator = (const bint &r)
{
memcpy(this, &r, ( + 1) * sizeof(int));
return *this;
}
};
bool operator < (const bint &a, const bint &b)
{
int i;
if ( != )
{
return < ;
}
for (i = - 1; i >= 0 && [i] == [i]; i--) ;
return i < 0 ? 0 : [i] < [i];
}
bool operator <= (const bint &a, const bint &b)
{
return !(b < a);
}
bint operator + (const bint &a, const bint &b)
{
bint res;
int i, cy = 0;
for (i = 0; i < || i < || cy > 0; i++)
{
if (i < )
{
cy += [i];
}
if (i < )
{
cy += [i];
}
[i] = cy % base;
cy /= base;
}
= i;
return res;
}
bint operator - (const bint &a, const bint &b)
{
bint res;
int i, cy = 0;
for ( = , i = 0; i < ; i++)
{
[i] = [i] - cy;
if (i < )
{
[i] -= [i];
}
if ([i] < 0)
{
cy = 1, [i] += base;
}
else
{
cy = 0;
}
}
while ( > 0 && [ - 1] == 0)
{
--;
}
return res;
}
bint operator * (const bint &a, const bint &b)
{
bint res;
= 0;
if (0 == )
{
[0] = 0;
return res;
}
int i, j, cy;
for (i = 0; i < ; i++)
{
for (j = cy = 0; j < || cy > 0; j++, cy /= base)
{
if (j < )
{
cy += [i] * [j];
}
if (i + j < )
{
cy += [i + j];
}
if (i + j >= )
{
[++] = cy % base;
}
else
{
[i + j] = cy % base;
}
}
}
return res;
}
bint operator / (const bint &a, const bint &b)
{ // !b != 0
bint tmp, mod, res;
int i, lf, rg, mid;
[0] = = 0;
for (i = - 1; i >= 0; i--)
{
mod = mod * base + [i];
for (lf = 0, rg = base -1; lf < rg;)
{
mid = (lf + rg + 1) / 2;
if (b * mid <= mod)
{
lf = mid;
}
else
{
rg = mid - 1;
}
}
[i] = lf;
mod = mod - b * lf;
}
= ;
while ( > 0 && [ - 1] == 0)
{
--;
}
return res; // return mod; 就是%运算
}
int digits(bint& a) // 返回位数
{
if ( == 0)
{
return 0;
}
int l = ( - 1) * 4;
for (int t = [ - 1]; t; ++l, t /= 10);
return l;
}
bool read(bint &b, char buf[]) // 读取失败返回0
{
if (1 != scanf("%s", buf))
{
return 0;
}
int w, u, ln = (int)strlen(buf);
memset(&b, 0, sizeof(bint));
if ('0' == buf[0] && 0 == buf[1])
{
return 1;
}
for (w = 1, u = 0; ln; )
{
u += (buf[--ln] - '0') * w;
if (w * 10 == base)
{
[++] = u;
w = 1;
u = 0;
}
else
{
w *= 10;
}
}
if (w != 1)
{
[++] = u;
}
return 1;
}
void write(const bint &v)
{
int i;
printf("%d", == 0 ? 0 : [ - 1]);
for (i = - 2; i >= 0; i--)
{
printf("%04d", [i]); // !!! 4 == width
}
printf("\n");
return ;
}
char buf[MAXC];
int main()
{
bint A, B, C, D;
read(A, buf);
read(B, buf);
C = A / B; // floor(A/B)
write(C);
D = B * C;
D = A - D; // A%B
write(D);
return 0;
}2017.8.6 修改 高效大数运算 代码
加强版大数运算
typedef long long ll;
class BigInteger
{
private:
const static int MOD = (119 << 23) + 1;
const static int root = 3;
const static int invroot = 332748118;
int *a;
int length, sig;
void apply(int length)
{
if (!length)
{
return ;
}
a = new int [length]();
this -> length = length;
}
void destroy()
{
if (!length)
{
return ;
}
delete [] a;
a = nullptr;
}
void resize(int length)
{
if (length == this->length)
{
return ;
}
if (!length)
{
return destroy();
}
int *aux = a;
a = new int [length]();
memcpy(a, aux, sizeof(int) * min(length, this->length));
if (this->length)
{
delete [] aux;
}
this->length = length;
}
BigInteger(int length) : length(length), sig(0)
{
apply(length);
}
BigInteger(const BigInteger &p, int length) : length(length), sig()
{
apply(length);
memcpy(a, , sizeof(int) * min(, length));
}
bool absgreaterequal(const BigInteger &q) const &
{
if (length != )
{
return length > ;
}
for (int i = length - 1; ~i; -- i)
{
if (a[i] > [i])
{
return true;
}
if (a[i] < [i])
{
return false;
}
}
return true;
}
BigInteger operator << (const int &dis) const &
{
if (!sig)
{
return *this;
}
BigInteger ret(length + dis);
memcpy( + dis, a, sizeof(int) * length);
= sig;
return ret;
}
BigInteger operator >> (const int &dis) const &
{
if (dis >= length)
{
return BigInteger();
}
BigInteger ret(length - dis);
memcpy(, a + dis, sizeof(int) * );
= sig;
return ret;
}
int powermod(int a, int exp) const &
{
int ret = 1;
for (; exp; exp >>= 1)
{
if (exp & 1)
{
ret = (ll) ret * a % MOD;
}
a = (ll) a * a % MOD;
}
return ret;
}
void NTT(int *a, int length, int type) const &
{
int len = -1;
for (int x = length; x; ++len, x >>= 1) ;
for (int i = 1, j = 0; i < length - 1; ++i)
{
for (int s = length; j ^= s >>= 1, ~j & s; ) ;
if (i < j)
{
swap(a[i], a[j]);
}
}
for (int i = 1; i <= len; ++ i)
{
for (int j = 0, unit = powermod(type == 1 ? root : invroot, (MOD - 1) >> i), szk = 1 << (i - 1); j < length; j += 1 << i)
{
for (int k = j, w = 1; k < j + szk; ++ k)
{
int s = a[k], t = (ll) w * a[k + szk] % MOD;
a[k] = s + t >= MOD ? s + t - MOD : s + t;
a[k + szk] = s - t < 0 ? s - t + MOD : s - t;
w = (ll) w * unit % MOD;
}
}
}
if (type == 1)
{
return ;
}
int inv = powermod(length, MOD - 2);
for (int i = 0; i < length; ++i)
{
a[i] = (ll) a[i] * inv % MOD;
}
}
int divide(BigInteger &p, const int &q) const &
{
if (!q)
{
assert(-1);
}
if (!)
{
return 0;
}
ll remain = 0, x = abs(q);
for (int i = length - 1; ~i; -- i)
{
remain = remain * 10 + [i];
[i] = (int)(remain / x);
remain %= x;
}
for (; && ![ - 1]; -- ) ;
remain *= ;
*= q < 0 ? -1 : 1;
if (!)
{
= 0;
}
return (int)remain;
}
public:
BigInteger() : length(0), sig(0) { a = nullptr; }
BigInteger(const BigInteger &p) : length(), sig()
{
apply(length), memcpy(a, , sizeof(int) * length);
}
~BigInteger() { destroy(); }
int getlength() { return length; }
bool positive() { return sig > 0; }
bool iszero() { return !sig; }
bool negative() { return sig < 0; }
bool even() { return !sig || !(a[0] & 1); }
BigInteger &operator = (const BigInteger &p)
{
destroy();
apply();
length = ;
sig = ;
memcpy(a, , sizeof(int) * length);
return *this;
}
template <typename T>
BigInteger &operator = (const T &p)
{
destroy();
sig = p ? p > 0 ? 1 : -1 : 0;
apply(40);
int cnt = 0;
for (T x = abs(p); x; x /= 10)
{
a[cnt++] = x % 10;
}
resize(cnt);
return *this;
}
void read()
{
destroy();
sig = 1;
char ch = getchar();
for ( ; ch < '0' || ch > '9'; ch = getchar())
{
if (ch == '-')
{
sig = -1;
}
}
resize(1);
int nowlength = 0;
for (; ch >= '0' && ch <= '9'; ch = getchar())
{
a[nowlength++] = ch - '0';
if (nowlength == length)
{
resize(length << 1);
}
}
reverse(a, a + nowlength);
for (; nowlength && !a[nowlength - 1]; --nowlength) ;
resize(nowlength);
sig = length ? sig : 0;
}
void write()
{
if (!sig)
{
return (void)putchar('0');
}
if (sig < 0)
{
putchar('-');
}
for (int i = length - 1; ~i; i--)
{
putchar(a[i] + '0');
}
}
template <typename T>
T tointeger()
{
T ret = 0;
for (int i = length - 1; i >= 0; ++ i)
{
ret = ret * 10 + a[i];
}
return ret * sig;
}
bool operator == (const BigInteger &p) const &
{
if (sig != || length != )
{
return false;
}
for (int i = 0; i < length; ++i)
{
if (a[i] != [i])
{
return false;
}
}
return true;
}
bool operator > (const BigInteger &p) const &
{
if (sig != )
{
return sig > ;
}
if (length != )
{
return length > ^ sig == -1;
}
for (int i = length - 1; i >= 0; --i)
{
if (a[i] > [i])
{
return sig > 0;
}
if (a[i] < [i])
{
return sig < 0;
}
}
return false;
}
BigInteger &operator ++ ()
{
resize(length + 1);
sig >= 0 ? ++a[0] : --a[0];
for (int i = 0; i < length - 1; ++i)
{
if (a[i] < 10 && a[i] >= 0)
{
break;
}
a[i] >= 10 ? (a[i] -= 10, ++a[i + 1]) : (a[i] += 10, --a[i + 1]);
}
for (; length && !a[length - 1]; --length) ;
resize(length);
sig = length ? sig >= 0 ? 1 : -1 : 0;
return *this;
}
BigInteger &operator -- ()
{
sig = -sig;
++*this;
sig = -sig;
return *this;
}
BigInteger operator ++ (int)
{
BigInteger aux(*this);
++*this;
return aux;
}
BigInteger operator -- (int)
{
BigInteger aux(*this);
--*this;
return aux;
}
BigInteger operator + (const BigInteger &p) const &
{
if (!)
{
return *this;
}
if (!sig)
{
return p;
}
bool type = true, flag = sig > 0;
const BigInteger *aux = this, *aux1 = &p;
if (sig != )
{
type = false;
if (!absgreaterequal(p))
{
flag = !flag;
swap(aux, aux1);
}
}
BigInteger ret(*aux, max(length, ) + 1);
for (int i = 0; i < - 1; ++i)
{
[i] += i < aux1->length ? type ? aux1->a[i] : -aux1->a[i] : 0;
[i] >= 10 ? ([i] -= 10, ++[i + 1]) : [i] < 0 ? ([i] += 10, --[i + 1]) : 0;
}
for (; && ![ - 1]; --) ;
();
= ? flag ? 1 : -1 : 0;
return ret;
}
BigInteger operator - () const &
{
BigInteger ret(*this);
= -;
return ret;
}
BigInteger operator - (const BigInteger &p) const & { return *this + (-p); }
BigInteger operator * (const BigInteger &p) const &
{
if (!sig || !)
{
return BigInteger();
}
int n = length + ;
int lengthret = 1;
for (; lengthret < n; lengthret <<= 1) ;
BigInteger ret(*this, lengthret);
int *aux = new int [lengthret]();
memcpy(aux, , sizeof(int) * );
NTT(, lengthret, 1);
NTT(aux, lengthret, 1);
for (int i = 0; i < lengthret; ++i)
{
[i] = (ll) [i] * aux[i] % MOD;
}
NTT(, lengthret, -1);
for (int i = 0; i < n - 1; i++)
{
[i + 1] += [i] / 10;
[i] %= 10;
}
for (; n && ![n - 1]; --n) ;
(n);
= sig * ;
return ret;
}
BigInteger operator * (const int &p) const &
{
if (!p || !sig)
{
return BigInteger();
}
BigInteger ret(*this, length + 10);
ll x = abs(p), remain = 0;
for (int i = 0; i < length; ++ i)
{
remain += [i] * x;
[i] = remain % 10;
remain /= 10;
}
int nowlength = length;
for ([nowlength] = (int)remain; [nowlength]; ++nowlength)
{
[nowlength + 1] = [nowlength] / 10;
[nowlength] %= 10;
}
for (; nowlength && ![nowlength - 1]; --nowlength) ;
(nowlength);
= sig * (p < 0 ? -1 : 1);
return ret;
}
BigInteger operator / (const BigInteger &p) const &
{
if (!)
{
assert(-1);
}
if (!sig || length < )
{
return BigInteger();
}
int num = 0;
for (int i = - 1; i >= - 3; --i)
{
(num *= 10) += i >= 0 ? [i] : 0;
}
num = 100000 / num;
int nowprecision = 1;
BigInteger ret;
ret = num;
for (; nowprecision <= length - ; nowprecision <<= 1)
{
BigInteger aux((nowprecision << 1) + 3);
= 1;
for (int i = - ; i < ; ++i)
{
[i - + ] = i >= 0 ? [i] : 0;
}
aux = (aux * ret >> (nowprecision + 2)) * ret >> (nowprecision + 2);
ret = (ret * 2 << nowprecision) - aux;
}
ret = ret * *this >> ( + nowprecision + 1);
= abs();
BigInteger aux(p);
= abs();
if (!absgreaterequal(ret * aux))
{
--ret;
}
else if (!absgreaterequal(++ret * aux))
{
--ret;
}
*= sig * ;
return ret;
}
BigInteger operator / (const int &p) const &
{
BigInteger ret(*this);
divide(ret, p);
();
return ret;
}
BigInteger sqrt() const &
{
if (sig < 0)
{
assert(-1);
}
if (!sig)
{
return *this;
}
int num = 0;
for (int i = length - 1; i >= length - 8; --i)
{
(num *= 10) += i >= 0 ? a[i] : 0;
}
ll x = length & 1 ? 10000000000000ll : 100000000000000ll;
num = std::sqrt(1.0 * x / num); // 命名空间不能省
int nowprecision = 2;
BigInteger ret;
ret = num;
for (; nowprecision <= (length >> 1) + 1; nowprecision = (nowprecision << 1) - 1)
{
BigInteger aux((nowprecision << 1) + 1 + (length & 1));
= 1;
for (int i = length - ; i < length; ++i)
{
[i - length + ] = i >= 0 ? a[i] : 0;
}
aux = ((aux * ret >> (nowprecision + 1)) * ret >> (nowprecision + 1)) / 2;
BigInteger aux1((nowprecision + 1) << 1);
= 1;
[ - 1] = 1, [ - 2] = 5;
ret = ret * (aux1 - aux) >> (nowprecision + 2);
}
ret = ret * *this >> ((length >> 1) + nowprecision + 1);
if (!absgreaterequal(ret * ret))
{
--ret;
}
else
{
++ret;
if (!absgreaterequal(ret * ret))
{
--ret;
}
}
return ret;
}
BigInteger operator % (const BigInteger &p) const &
{
if (!)
{
assert(-1);
}
return *this - *this / p * p;
}
int operator % (const int &p) const &
{
if (!p)
{
assert(-1);
}
BigInteger aux(*this);
return divide(aux, p);
}
friend BigInteger operator * (const int &q, const BigInteger &p) { return p * q; }
BigInteger &operator += (const BigInteger &p) { *this = *this + p; return *this; }
BigInteger &operator -= (const BigInteger &p) { *this = *this - p; return *this; }
BigInteger &operator *= (const BigInteger &p) { *this = *this * p; return *this; }
BigInteger &operator *= (const int &p) { *this = *this * p; return *this; }
BigInteger &operator /= (const BigInteger &p) { *this = *this / p; return *this; }
BigInteger &operator /= (const int &p) { *this = *this / p; return *this; }
BigInteger &operator %= (const BigInteger &p) { *this = *this % p; return *this; }
BigInteger &operator %= (const int &p) { *this = *this % p; return *this; }
template <typename T>
BigInteger power(T exp) const &
{
BigInteger ret = 1, aux(*this);
for (; exp; exp >>= 1)
{
if (exp & 1)
{
ret *= aux;
}
aux *= aux;
}
return ret;
}
};
BigInteger a;
int main()
{
();
a.sqrt().write();
putchar(10);
return 0;
}2017.8.6 添加 加强版大数运算
2018.5.11 修改 不只是四则运算，包含开方取模