ii. Big Integers and Fractions

C++ has no built-in big integers or rationals. Contest problems needing them usually want a way to avoid them, sometimes a small hand-rolled implementation. Python and Java have arbitrary precision built in: if the task is purely big-integer arithmetic and the judge allows it, using Python is legitimate and far faster to write.

Instead of big integers / fractions	Use
the exact value of a huge count	the answer modulo a prime (most problems ask for this)
comparing huge products $ab$ vs $cd$, $\frac{a}{b}$ vs $\frac{c}{d}$	__int128 cross-multiplication, or logarithms with care
$a^b\mathrm{mod}m$	fast exponentiation
exact $n!$	factorials mod $p$, or Legendre’s formula for prime exponents
divisibility / residue of a $10^5$-digit input	process the digits: r = (r * 10 + d) % M; digit DP
values up to $\approx 1.7\cdot 10^{38}$	__int128 (all arithmetic, no cin/cout: write helpers)
a rational answer	$P\cdot Q^{-1}\mathrm{mod}998244353$: the modern convention, exact and overflow-free (modular inverse)
money, percentages, inputs with a stated number of decimals	fixed point: scale to integers, llround(dollars * 100)
exact linear algebra	Bareiss (fraction-free): Determinants
geometry with rational points	keep (num_x, num_y, den) triples
probabilities	modular inverses

__int128 I/O and a minimal big integer

void printI128(i128 x) {
    if (x < 0) { putchar('-'); x = -x; }
    if (x > 9) printI128(x / 10);
    putchar('0' + int(x % 10));
}
i128 readI128(const string& s) { i128 r = 0; int i = s[0] == '-'; for (int j = i; j < sz(s); j++) r = r * 10 + (s[j] - '0'); return i ? -r : r; }
 
struct Big {                                               // non-negative, base 10^9, least significant limb first
    static const ll BASE = 1000000000;
    vector<ll> d;
    Big(ll v = 0) { while (v) d.push_back(v % BASE), v /= BASE; }
    Big(const string& s) { for (int i = sz(s); i > 0; i -= 9) d.push_back(stoll(s.substr(max(0, i - 9), i - max(0, i - 9)))); trim(); }
    void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }
    friend int cmp(const Big& a, const Big& b) {
        if (sz(a.d) != sz(b.d)) return sz(a.d) < sz(b.d) ? -1 : 1;
        for (int i = sz(a.d) - 1; i >= 0; i--) if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
        return 0;
    }
    bool operator<(const Big& o) const { return cmp(*this, o) < 0; }
    bool operator==(const Big& o) const { return cmp(*this, o) == 0; }
    Big operator+(const Big& o) const {
        Big r; ll carry = 0;
        for (int i = 0; i < max(sz(d), sz(o.d)) || carry; i++) {
            ll cur = carry + (i < sz(d) ? d[i] : 0) + (i < sz(o.d) ? o.d[i] : 0);
            r.d.push_back(cur % BASE); carry = cur / BASE;
        }
        return r;
    }
    Big operator-(const Big& o) const {                    // requires *this >= o
        Big r = *this; ll borrow = 0;
        for (int i = 0; i < sz(r.d); i++) {
            r.d[i] -= borrow + (i < sz(o.d) ? o.d[i] : 0);
            borrow = r.d[i] < 0; if (borrow) r.d[i] += BASE;
        }
        r.trim(); return r;
    }
    Big operator*(const Big& o) const {                    // schoolbook O(n m)
        if (d.empty() || o.d.empty()) return Big();
        vector<ull> t(sz(d) + sz(o.d) + 1, 0);
        for (int i = 0; i < sz(d); i++) {
            ull carry = 0;
            for (int j = 0; j < sz(o.d) || carry; j++) {
                ull cur = t[i + j] + carry + (j < sz(o.d) ? (ull)d[i] * o.d[j] : 0);
                t[i + j] = cur % BASE; carry = cur / BASE;
            }
        }
        Big r; r.d.assign(all(t)); r.trim(); return r;
    }
    pair<Big, ll> divmod(ll m) const {                     // by a small positive integer
        Big q; q.d.resize(sz(d)); ll rem = 0;
        for (int i = sz(d) - 1; i >= 0; i--) { i128 cur = (i128)rem * BASE + d[i]; q.d[i] = ll(cur / m); rem = ll(cur % m); }
        q.trim(); return {q, rem};
    }
    pair<Big, Big> divmod(const Big& b) const {            // long division by a Big, O(n m log BASE)
        Big q, r; q.d.resize(sz(d));
        for (int i = sz(d) - 1; i >= 0; i--) {
            r.d.insert(r.d.begin(), d[i]); r.trim();      // r = r * BASE + d[i]
            ll lo = 0, hi = BASE - 1;                      // largest x with b * x <= r
            while (lo < hi) { ll mid = (lo + hi + 1) / 2; if (cmp(b * Big(mid), r) <= 0) lo = mid; else hi = mid - 1; }
            q.d[i] = lo; r = r - b * Big(lo);
        }
        q.trim(); return {q, r};
    }
    string str() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());
        for (int i = sz(d) - 2; i >= 0; i--) { string t = to_string(d[i]); s += string(9 - sz(t), '0') + t; }
        return s;
    }
};

Multiplication	Time	Typical crossover
schoolbook	$O(n^2)$	below ~30 limbs
Karatsuba	$O(n^{1.585})$	30–300
Toom–Cook 3	$O(n^{1.465})$	300–3000
FFT / NTT	$O(n\log n)$	above ~3000 limbs: FFT
Schönhage–Strassen	$O(n\log n\log \log n)$	very large

Schoolbook in base $10^9$ handles numbers with thousands of digits comfortably. For $10^5$-digit products use FFT with a small base ($10^3$ or $10^4$) so that convolution values stay within double precision, or NTT with CRT. Big-integer division in libraries uses Newton’s iteration for the reciprocal, $x\leftarrow x(2-ax)$ (Root Finding); the long division above is enough for contests.

Proof: the big-integer routines

All routines are the schoolbook algorithms in base $B=10^9$. Addition and subtraction: a limb sum is $<2B$ and a limb difference is $>-B-1$, so one carry or borrow bit propagates the exact result. Multiplication: a partial product is $<B^2=10^{18}$, and t[i+j] + carry + product stays below $2^{64}$ because t[i+j] < B and the carry is $<2\cdot 10^9$; the convolution with carries computes ${\sum }_{i,j}{a}_i{b}_j{B}^{i+j}$. Short division: at each step cur $=rem\cdot B+d_i<m\cdot B$ (since $rem<m$), so quotient digits are $<B$ and the invariant “value processed so far $=q\cdot m+rem$” holds. Long division: invariant: after processing limb $i$, the prefix of the dividend equals $q_{\text{prefix}}\cdot b+r$ with $0\le r<b$. Appending a limb gives $r^{\prime }=rB+d_i<bB$, so the next quotient digit $x=\lfloor r^{\prime }/b\rfloor$ is $<B$ and is found by binary search on $b\cdot x\le r^{\prime }$. Checked against __int128 arithmetic on random values below $10^{36}$ and by the identities $(ab)/b=a$, $qb+r=a$ with $0\le r<b$ on random 200-digit numbers.

Fractions

Represent $\frac{p}{q}$ as a reduced pair: exact, comparable, free of floating-point questions, at the cost of overflow risk. Normalise after every operation (otherwise denominators explode), compare with __int128 cross-multiplication (otherwise comparison overflows long before the values do), and cross-cancel before multiplying.

struct Frac {
    ll p, q;                                               // q > 0, gcd(|p|, q) = 1
    Frac(ll p = 0, ll q = 1) : p(p), q(q) { norm(); }
    void norm() { if (q < 0) p = -p, q = -q; ll g = gcd(llabs(p), q); if (g) p /= g, q /= g; else q = 1; }
    Frac operator+(const Frac& o) const { ll g = gcd(q, o.q); return Frac(p * (o.q / g) + o.p * (q / g), q / g * o.q); }
    Frac operator-(const Frac& o) const { return *this + Frac(-o.p, o.q); }
    Frac operator*(const Frac& o) const {                  // cross-cancel first
        ll g1 = max(1LL, gcd(llabs(p), o.q)), g2 = max(1LL, gcd(llabs(o.p), q));
        return Frac((p / g1) * (o.p / g2), (q / g2) * (o.q / g1));
    }
    Frac operator/(const Frac& o) const { return *this * Frac(o.q, o.p); }
    bool operator<(const Frac& o) const { return (i128)p * o.q < (i128)o.p * q; }
    bool operator==(const Frac& o) const { return p == o.p && q == o.q; }
};
 
// Simplest fraction (smallest denominator, then numerator) strictly between p1/q1 and p2/q2, 0 <= p1/q1 < p2/q2.
// This is the first fraction met when descending the Stern-Brocot tree; O(log) steps (continued fractions).
pair<ll, ll> simplestBetween(ll p1, ll q1, ll p2, ll q2) {
    ll k = p1 / q1;                                        // floor of the lower bound
    if ((i128)(k + 1) * q2 < p2) return {k + 1, 1};        // an integer fits strictly inside
    ll r1 = p1 - k * q1, r2 = p2 - k * q2;                 // shift both bounds by k: now in [0, 1]
    if (r1 == 0) { ll y = q2 / r2 + 1; return {k * y + 1, y}; }   // x - k in (0, r2/q2): take 1/y
    auto [a, b] = simplestBetween(q2, r2, q1, r1);         // reciprocal y = 1/(x - k) in (q2/r2, q1/r1)
    return {k * a + b, a};                                 // x = k + b/a
}
 
pair<ll, ll> fareyNext(ll a, ll b, ll p, ll q, ll n) {     // term after p/q in F_n, given the previous term a/b
    ll k = (n + b) / q;
    return {k * p - a, k * q - b};
}

Fraction arithmetic	Feasible?
a handful of operations	yes
sorting / comparing $n$ given fractions	yes: comparison does not grow anything
summing hundreds of fractions	no: denominators up to $D^n$, overflow
Gaussian elimination with fractions	overflows quickly: use Bareiss or work mod $p$

Stern–Brocot tree. Starting from $\frac{0}{1}$ and $\frac{1}{0}$, repeatedly inserting mediants $\frac{a+c}{b+d}$ produces every positive rational exactly once, in a binary search tree. The path to $\frac{p}{q}$ is its continued fraction (runs of left and right moves are the partial quotients), so the descent in simplestBetween jumps a whole run at a time. Uses: the simplest fraction in an interval, best rational approximation with a bounded denominator, and the simplicity rule for game values (Hackenbush).

Farey sequences. $F_n$ is the sorted list of reduced fractions in $[0,1]$ with denominator $\le n$; it has $1+{\sum }_{i=1}^n\phi (i)$ terms, and consecutive terms $\frac{a}{b}<\frac{c}{d}$ satisfy $bc-ad=1$, which gives the $O(1)$ step fareyNext (enumerate fractions in order without sorting; count coprime pairs: Arithmetic Functions).

Continued fractions. $\frac{p}{q}=a_0+\frac{1}{a_1+\frac{1}{a_2+\cdots }}$ with the $a_i$ exactly the quotients of the Euclidean algorithm on $(p,q)$; the convergents are the best rational approximations, which Pell’s equation exploits.

Proof: simplestBetween and the Farey step

Simplest fraction. If an integer lies strictly inside, the smallest such integer $k+1$ has denominator 1 and is the answer. Otherwise the interval lies in $[k,k+1]$ and every fraction inside is $k+\frac{1}{y}$ with $y>1$; writing $x-k=\frac{b}{a}$, the denominator of $x$ is $a$, the numerator of $y=\frac{a}{b}$. Minimising the denominator of $x$ is therefore minimising the numerator of $y$ over the reciprocal interval $(\frac{q_2}{r_2},\frac{q_1}{r_1})$; and the simplest fraction of an interval with lower bound $\ge 1$ simultaneously minimises numerator and denominator (in the Stern–Brocot tree, the first fraction met in an interval is an ancestor of all others in it, and ancestors have smaller numerator and denominator). If $r_1=0$, the interval for $x-k$ is $(0,\frac{r_2}{q_2})$, whose simplest member is $\frac{1}{y}$ with the least $y>\frac{q_2}{r_2}$. Each recursion is one step of the Euclidean algorithm on the bounds, so the depth is $O(\log )$.

Farey step. For consecutive terms $\frac{a}{b}<\frac{p}{q}$ of $F_n$, $pb-aq=1$. The next term $\frac{p^{\prime }}{q^{\prime }}$ satisfies $p^{\prime }q-p{q}^{\prime }=1$; all solutions are $(p^{\prime },q^{\prime })=(kp-a,kq-b)$, and the next term is the one with the largest denominator $kq-b\le n$ (larger denominators give fractions closer to $\frac{p}{q}$), i.e. $k=\lfloor \frac{n+b}{q}\rfloor$. Checked: simplestBetween against a brute-force search by denominator, and fareyNext against sorted Farey sequences for $n\le 40$.

Related notes

• Continued Fractions and Pell
• Floating Point
• C++ for CP (integer types and overflow)