Big Integer Arithmetic

C++ has no built-in big integers, so contest problems needing them either want a small hand-rolled implementation or (more often) a way to avoid them.

Avoid it first

Instead of big integers	Use
The exact value of a huge count	the answer modulo a prime — most problems ask for this
Comparing huge products $ab$ vs $cd$	__int128, or compare logarithms with care
$a^b\mathrm{mod}m$	fast exponentiation
Exact $n!$	factorials mod p, or Legendre’s formula for the exponents
Checking divisibility of a huge number	digit DP, or modular arithmetic on the digits
Exact fractions	pair<long long,long long> reduced by the gcd
Values up to $10^{36}$	__int128

__int128 covers most of the gap: it holds up to $1.7\cdot 10^{38}$, supports all arithmetic, and costs nothing to use. It has no cin/cout support, so write small read/print helpers.

void print(__int128 x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) print(x / 10);
    putchar('0' + (int)(x % 10));
}

A minimal big integer

Base $10^9$ (fits a product in long long), little-endian limbs:

struct Big {
    static const long long BASE = 1000000000;
    vector<long long> d;                                // least significant first
 
    Big(long long v = 0) { while (v) { d.push_back(v % BASE); v /= BASE; } }
 
    void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }
 
    Big operator+(const Big& o) const {
        Big r; long long carry = 0;
        for (size_t i = 0; i < max(d.size(), o.d.size()) || carry; i++) {
            long long cur = carry;
            if (i < d.size())   cur += d[i];
            if (i < o.d.size()) cur += o.d[i];
            r.d.push_back(cur % BASE);
            carry = cur / BASE;
        }
        return r;
    }
 
    Big operator*(const Big& o) const {
        vector<long long> r(d.size() + o.d.size(), 0);
        for (size_t i = 0; i < d.size(); i++) {
            long long carry = 0;
            for (size_t j = 0; j < o.d.size() || carry; j++) {
                long long cur = r[i+j] + carry + (j < o.d.size() ? d[i] * o.d[j] : 0);
                r[i+j] = cur % BASE;
                carry = cur / BASE;
            }
        }
        Big res; res.d = r; res.trim();
        return res;
    }
 
    string str() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        for (int i = d.size() - 2; i >= 0; i--) {
            string t = to_string(d[i]);
            s += string(9 - t.size(), '0') + t;
        }
        return s;
    }
};

Addition and multiplication cover most needs. Subtraction, comparison and division-by-a-small-integer are each a dozen more lines; full big-integer division is considerably harder.

Multiplication complexity

Method	Time	Crossover
Schoolbook	$O(n^2)$	< ~30 limbs
Karatsuba	$O(n^{1.585})$	30-300
Toom-Cook 3	$O(n^{1.465})$	300-3000
FFT	$O(n\log n)$	> ~3000
Schönhage-Strassen	$O(n\log n\log \log n)$	very large

For contests, schoolbook in base $10^9$ handles numbers with thousands of digits comfortably. If you genuinely need $10^5$-digit multiplication, use FFT with a smaller base (e.g. $10^3$ or $10^4$) to keep the convolution values inside double precision.

Other languages

Python and Java have arbitrary-precision integers built in. If the problem is purely big-integer arithmetic and the judge allows it, using Python is entirely legitimate and far faster to write.

Fixed-point as an alternative

For problems with a bounded number of decimal places, scale everything to integers:

long long cents = (long long)llround(dollars * 100);

Exact, fast, and it eliminates every floating-point comparison question. This is the right approach for money, percentages, and any input with a stated precision.

Modular arithmetic on huge inputs

When the input is a number with $10^5$ digits given as a string, you rarely need to store it — process the digits:

long long mod = 0;
for (char c : s) mod = (mod * 10 + (c - '0')) % M;

This handles “is this 100000-digit number divisible by $m$”, “what is it mod $p$”, and feeds directly into digit DP.

See also: Big Integer Multiplication · Exact Rational Arithmetic · Modular Arithmetic