Сложная длинная арифметика
Перейти к навигации
Перейти к поиску
Более эффективные длинные целые
class PrintHelper {
int d[1000], size;
public:
PrintHelper() {
d[0] = 0;
size = 1;
}
void add1() {
d[0]++;
}
void mul2() {
int carry = 0;
for (int i = 0; i < size; i++) {
int x = d[i] * 2 + carry;
d[i] = x % 10;
carry = x / 10;
}
if (carry)
d[size++] = 1;
}
void print() const {
for (int i = size - 1; i >= 0; i--)
printf("%d", d[i]);
printf("\n");
}
};
class BigInteger {
static const int MAX_SIZE = 100;
static const unsigned int MASK = ~(1 << 31);
unsigned int d[MAX_SIZE];
int size;
public:
BigInteger(unsigned long long val = 0) {
for (int i = 0; i < MAX_SIZE; i++)
d[i] = 0;
size = 0;
if (val == 0)
d[size++] = 0;
while (val > 0) {
d[size++] = val & MASK;
val >>= 31;
}
}
void print() const {
PrintHelper p;
for (int i = size - 1; i >= 0; i--) {
for (int bit = 30; bit >= 0; bit--) {
p.mul2();
if ((d[i] >> bit) & 1)
p.add1();
}
}
p.print();
}
int cmp(const BigInteger &that) const {
if (size != that.size)
return size < that.size ? -1 : 1;
for (int i = size - 1; i >= 0; i--) {
if (d[i] != that.d[i])
return d[i] < that.d[i] ? -1 : 1;
}
return 0;
}
bool operator < (const BigInteger &that) const {
return cmp(that) < 0;
}
bool operator == (const BigInteger &that) const {
return cmp(that) == 0;
}
BigInteger &operator += (const BigInteger &that) {
unsigned int carry = 0;
for (int i = 0; i < max(size, that.size) || carry != 0; i++) {
unsigned long long x = 0ULL + d[i] + that.d[i] + carry;
d[i] = x & MASK;
carry = x >> 31;
}
size = max(size, that.size) + 1;
while (size > 1 && d[size - 1] == 0)
size--;
return *this;
}
BigInteger operator + (const BigInteger &that) const {
BigInteger res = *this;
return res += that;
}
BigInteger &operator -= (const BigInteger &that) {
int carry = 0;
for (int i = 0; i < size || carry != 0; i++) {
long long x = 0LL + d[i] - that.d[i] + carry;
d[i] = (x + (1ULL << 31)) & MASK;
carry = x < 0 ? -1 : 0;
}
while (size > 1 && d[size - 1] == 0)
size--;
return *this;
}
BigInteger operator - (const BigInteger &that) const {
BigInteger res = *this;
return res -= that;
}
BigInteger &operator *= (const BigInteger &that) {
unsigned int rd[MAX_SIZE] = {};
for (int i = 0; i < size; i++) {
unsigned int carry = 0;
for (int j = 0; j < that.size || carry != 0; j++) {
unsigned long long x = rd[i + j] + 1ULL * d[i] * that.d[j] + carry;
rd[i + j] = x & MASK;
carry = x >> 31;
}
}
for (int i = 0; i < MAX_SIZE; i++)
d[i] = rd[i];
size = size + that.size;
while (size > 1 && d[size - 1] == 0)
size--;
return *this;
}
BigInteger operator * (const BigInteger &that) const {
BigInteger res = *this;
return res *= that;
}
BigInteger &operator *= (unsigned int that) {
unsigned int carry = 0;
for (int i = 0; i < size || carry != 0; i++) {
unsigned long long x = 1ULL * d[i] * that + carry;
d[i] = x & MASK;
carry = x >> 31;
}
size = size + 1;
while (size > 1 && d[size - 1] == 0)
size--;
return *this;
}
BigInteger operator * (unsigned int that) const {
BigInteger res = *this;
return res *= that;
}
BigInteger &operator /= (const BigInteger &that) {
BigInteger carry;
for (int i = size - 1; i >= 0; i--) {
carry *= (1ULL << 31);
carry.d[0] = d[i];
unsigned int l = 0, r = (1 << 31), m;
while (l + 1 < r) {
m = l + (r - l) / 2;
if ((that * m).cmp(carry) <= 0)
l = m;
else
r = m;
}
d[i] = l;
carry = carry - that * d[i];
}
while (size > 1 && d[size - 1] == 0)
size--;
return *this;
}
BigInteger operator / (const BigInteger &that) const {
BigInteger res = *this;
return res /= that;
}
BigInteger operator % (const BigInteger &that) const {
BigInteger carry;
for (int i = size - 1; i >= 0; i--) {
carry *= (1ULL << 31);
carry.d[0] = d[i];
unsigned int l = 0, r = (1 << 31), m;
while (l + 1 < r) {
m = l + (r - l) / 2;
if ((that * m).cmp(carry) <= 0)
l = m;
else
r = m;
}
unsigned int digit = l;
carry = carry - that * digit;
}
return carry;
}
BigInteger gcd(const BigInteger &that) const {
if (that == 0)
return *this;
return that.gcd(*this % that);
}
};
Длинные целые со знаком
class BigSignedInteger {
BigInteger a;
int sgn;
BigSignedInteger(const BigInteger &a, int sign) : a(a), sgn(sign) {}
public:
BigSignedInteger(long long val = 0) {
a = ::abs(val);
sgn = val ? val > 0 ? 1 : -1 : 0;
}
BigSignedInteger(const BigInteger &val) {
a = val;
sgn = val.cmp(0);
}
void print() const {
if (sgn == -1)
printf("-");
a.print();
}
BigInteger abs() const {
return a;
}
int sign() const {
return sgn;
}
int cmp(const BigSignedInteger &that) const {
if (sgn != that.sgn)
return sgn < that.sgn ? -1 : 1;
return sgn * a.cmp(that.a);
}
bool operator < (const BigSignedInteger &that) const {
return cmp(that) < 0;
}
bool operator == (const BigSignedInteger &that) const {
return cmp(that) == 0;
}
BigSignedInteger operator + (const BigSignedInteger &that) const {
if (sgn == 1) {
if (that.sgn == 1)
return BigSignedInteger(a + that.a, 1);
if (that.sgn == 0)
return *this;
if (that.sgn == -1) {
if (a > that.a)
return BigSignedInteger(a - that.a, 1);
if (a == that.a)
return 0;
if (a < that.a)
return BigSignedInteger(that.a - a, -1);
}
}
if (sgn == 0) {
return that;
}
if (sgn == -1) {
if (that.sgn == 1) {
if (a > that.a)
return BigSignedInteger(a - that.a, -1);
if (a == that.a)
return 0;
if (a < that.a)
return BigSignedInteger(that.a - a, 1);
}
if (that.sgn == 0)
return *this;
if (that.sgn == -1)
return BigSignedInteger(a + that.a, -1);
}
}
BigSignedInteger operator - (const BigSignedInteger &that) const {
if (sgn == 1) {
if (that.sgn == 1) {
if (a > that.a)
return BigSignedInteger(a - that.a, 1);
if (a == that.a)
return 0;
if (a < that.a)
return BigSignedInteger(that.a - a, -1);
}
if (that.sgn == 0)
return *this;
if (that.sgn == -1)
return BigSignedInteger(a + that.a, 1);
}
if (sgn == 0) {
return BigSignedInteger(that.abs(), -that.sign());
}
if (sgn == -1) {
if (that.sgn == 1)
return BigSignedInteger(a + that.a, -1);
if (that.sgn == 0)
return *this;
if (that.sgn == -1) {
if (a > that.a)
return BigSignedInteger(a - that.a, -1);
if (a == that.a)
return 0;
if (a < that.a)
return BigSignedInteger(that.a - a, 1);
}
}
}
BigSignedInteger operator * (const BigSignedInteger &that) const {
return BigSignedInteger(a * that.a, sgn * that.sgn);
}
BigSignedInteger operator / (const BigSignedInteger &that) const {
if (a < that.a)
return 0;
return BigSignedInteger(a / that.a, sgn / that.sgn);
}
};
Длинные рациональные числа со знаком
class BigRational {
BigSignedInteger n;
BigInteger d;
void normalize() {
BigInteger g = n.abs().gcd(d);
n = n / g;
d = d / g;
}
public:
BigRational(long long n = 0, long long d = 1) : n(n), d(d) {
normalize();
}
BigRational(const BigSignedInteger &n, const BigInteger &d) : n(n), d(d) {
normalize();
}
BigSignedInteger numerator() const {
return n;
}
int cmp(const BigRational &that) const {
return (n * that.d).cmp(that.n * d);
}
bool operator < (const BigRational &that) const {
return cmp(that) < 0;
}
bool operator == (const BigRational &that) const {
return cmp(that) == 0;
}
BigRational operator + (const BigRational &that) const {
return BigRational(n * that.d + that.n * d, d * that.d);
}
BigRational operator - (const BigRational &that) const {
return BigRational(n * that.d - that.n * d, d * that.d);
}
BigRational operator * (const BigRational &that) const {
return BigRational(n * that.n, d * that.d);
}
BigRational operator / (const BigRational &that) const {
if (that.n.sign() == 1)
return BigRational(n * that.d, that.n.abs() * d);
if (that.n.sign() == -1)
return BigRational(n * that.d * -1, that.n.abs() * d);
}
};