Số lớn và __int128

Kiểu long long chỉ chứa được số nguyên tới khoảng $9,2·{10}^{18}$ (19 chữ số). Rất nhiều bài đếm, tổ hợp, giai thừa hay thứ hạng từ điển có đáp án vượt xa mức đó. Trang này trình bày bốn công cụ, xếp theo mức "nặng" tăng dần: ước lượng để biết khi nào thật sự cần số lớn, __int128 của GCC (tới khoảng $1,7·{10}^{38}$, gần như miễn phí), số lớn tự cài bằng mảng chữ số cơ số ${10}^9$ (cộng, trừ, so sánh, nhân/chia số nhỏ trong $O(n)$; nhân hai số lớn trong $O(nm)$ với $n,m$ là số khối), và số nguyên Python. Cuối cùng là mẹo chặn trên (saturating): khi chỉ cần so sánh số đếm với một ngưỡng $k$ thì không cần số lớn nào cả.

Ý tưởng / Trực giác

Bước 1: ước lượng độ lớn trước khi code

Trước khi viết một dòng số lớn nào, hãy hỏi: đáp án (và mọi giá trị trung gian) lớn cỡ bao nhiêu? Công cụ chính là đếm chữ số, tức ${\log }_{10}$:

• Tích của số $a$ chữ số và số $b$ chữ số có khoảng $a+b$ chữ số. Hai số cỡ ${10}^{18}$ nhân nhau được cỡ ${10}^{36}$: tràn long long nhưng vẫn vừa __int128.
• ${\log }_{10}(n!)={\sum }_{i=1}^n{\log }_{10}i$. Ví dụ $100!$ có $158$ chữ số, ${10}^5!$ có khoảng $456574$ chữ số.
• $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le 2^n$, và $2^{10}\approx {10}^3$ nên $2^n$ có khoảng $0,3n$ chữ số. Số Fibonacci $F_n\approx {\phi }^n/\sqrt{5}$ có khoảng $0,209n$ chữ số.

Bảng ngưỡng nên thuộc:

Dòng double đáng chú ý: double biểu diễn được số rất lớn (tới ${10}^{308}$) nhưng chỉ có $53$ bit định trị, nên mọi số nguyên trên $2^{53}$ có thể bị làm tròn. Không dùng double để lưu đáp án nguyên cần chính xác.

Từ bảng này suy ra quy trình chọn công cụ:

1. Đáp án và mọi giá trị trung gian $<9·{10}^{18}$: long long là đủ.
2. Chỉ một vài phép nhân vượt ngưỡng (tích hai số ${10}^{18}$, $a·bmodm$ với $m\approx {10}^{18}$), hoặc đáp án $<{10}^{38}$: dùng __int128.
3. Đáp án có hàng chục tới hàng nghìn chữ số và đề bắt in chính xác: cần số lớn (tự cài trong C++, hoặc Python).
4. Số đếm khổng lồ nhưng đề chỉ hỏi "có ít nhất $k$ không" hay "phần tử thứ $k$" với $k\le {10}^{18}$: chặn trên, không cần số lớn.

Bước 2: số lớn là "phép tính bằng tay" trên một mảng

Số lớn chỉ là cách ta tính bằng bút giấy ở tiểu học: viết số thành dãy chữ số, cộng từ phải sang trái kèm nhớ. Điểm khác duy nhất: thay vì mỗi ô một chữ số thập phân, ta để mỗi ô chứa $9$ chữ số, tức làm việc trong cơ số $B={10}^9$. Vì sao chọn ${10}^9$?

• Mỗi khối $<{10}^9$ vừa int. Tích hai khối $<{10}^{18}$, cộng thêm số nhớ vẫn vừa long long/unsigned long long. Đây là cơ số lớn nhất dạng ${10}^k$ còn nhân an toàn trong 64 bit.
• Số khối ít hơn $9$ lần so với cơ số $10$, nên nhanh hơn khoảng $9$ lần (và $81$ lần với phép nhân $O(nm)$).
• Vẫn là lũy thừa của $10$ nên đọc từ xâu và in ra xâu rất dễ: cắt/ghép theo nhóm $9$ chữ số.

Ta lưu các khối theo thứ tự ngược (little-endian): d[0] là khối thấp nhất. Nhờ vậy số nhớ lan về phía chỉ số tăng, và khi kết quả dài thêm chỉ cần push_back.

Bước 3: khi chỉ cần so sánh, hãy chặn trên

Nhiều bài "tìm phần tử thứ $k$ theo thứ tự từ điển" (xem hạng của hoán vị) hay "có ít nhất $k$ cách không" cần đếm số cách hoàn thành từ mỗi trạng thái. Số cách có thể tới $2^{1000}$, nhưng mọi thứ ta làm với nó chỉ là so sánh với $k\le {10}^{18}$ và trừ đi khi nó nhỏ hơn $k$. Vì vậy thay mọi giá trị $v$ bằng $min(v,\text{LIMIT})$ với $\text{LIMIT}>{10}^{18}$:

• Nếu $v$ thật $\ge \text{LIMIT}$ thì bản chặn bằng $\text{LIMIT}>k$: phép so sánh "$k\le v$" vẫn cho cùng kết quả.
• Nếu $v$ thật $<\text{LIMIT}$ thì bản chặn chính là $v$: đúng tuyệt đối.
• Ta chỉ trừ khi $v<k$, tức $v$ chính xác, nên phép trừ luôn đúng.

Phép cộng/nhân trên giá trị đã chặn phải không tràn: với $\text{LIMIT}=2·{10}^{18}$, tổng hai giá trị chặn $\le 4·{10}^{18}<9,2·{10}^{18}$ nên cộng rồi min là an toàn; phép nhân phải kiểm tra trước bằng phép chia.

Ví dụ chạy tay

Số lớn cơ số ${10}^9$: cộng, nhân số nhỏ, chia số nhỏ

Lấy $x=123456789012345678901$ và $y=98765432109876543210$. Cắt từ phải sang, mỗi khối $9$ chữ số:

x = 123 | 456789012 | 345678901      d = [345678901, 456789012, 123]
y =  98 | 765432109 | 876543210      d = [876543210, 765432109,  98]
          khối 2      khối 1   khối 0   (d[0] là khối thấp nhất)

Cộng từ khối $0$ lên, nhớ $1$ khi tổng $\ge {10}^9$:

i  x.d[i]      y.d[i]      nhớ vào   tổng           ghi (mod 1e9)   nhớ ra
0  345678901 + 876543210 + 0       = 1222222111  -> 222222111       1
1  456789012 + 765432109 + 1       = 1222221122  -> 222221122       1
2        123 +        98 + 1       =        222  -> 222             0

x + y = [222222111, 222221122, 222]  ->  "222" "222221122" "222222111"
      = 222222221122222222111

Nhân với số nhỏ $m=37$: mỗi khối nhân $m$ cộng nhớ, giữ phần dư cho ${10}^9$, phần thương thành nhớ:

i  x.d[i]*37 + nhớ vào       = cur          ghi          nhớ ra
0  345678901*37 + 0          = 12790119337  790119337    12
1  456789012*37 + 12         = 16901193456  901193456    16
2        123*37 + 16         =        4567  4567          0

37x = 4567 | 901193456 | 790119337 = 4567901193456790119337

Chia cho số nhỏ $m=37$: ngược lại, đi từ khối cao xuống, mang phần dư sang khối thấp hơn (như chia dọc):

i  cur = dư*1e9 + x.d[i]     thương khối   dư
2  0*1e9 + 123 = 123            3          12
1  12*1e9 + 456789012           336669973  11
0  11*1e9 + 345678901           306639970  11

x / 37 = [306639970, 336669973, 3] = 3336669973306639970,  x mod 37 = 11

Khi in, khối cao nhất in bình thường còn mọi khối sau phải đệm đủ $9$ chữ số: khối $5$ phải in thành 000000005, nếu không số sẽ bị "co" lại.

Nhân hai số lớn: tích chập các khối

Để dễ nhìn, dùng cơ số $100$: $1234\times 5678$, với $a=[34,12]$ và $b=[78,56]$. Khối $a_i$ nhân khối $b_j$ góp vào ô $i+j$:

          b0=78          b1=56
a0=34   34*78=2652     34*56=1904      -> ô 0, ô 1
a1=12   12*78= 936     12*56= 672      -> ô 1, ô 2

ô 0: 2652              -> ghi 52, nhớ 26
ô 1: 1904 + 936 + 26   = 2866 -> ghi 66, nhớ 28
ô 2: 672 + 28          = 700  -> ghi 00, nhớ 7
ô 3: 7                 -> ghi 7

kết quả: 7 | 00 | 66 | 52 = 7006652 = 1234 * 5678

Mỗi cặp $(i,j)$ được xét đúng một lần nên phép nhân tốn $O(nm)$ phép nhân khối.

Chặn trên: xâu nhị phân thứ $k$

Bài: liệt kê theo thứ tự từ điển các xâu nhị phân độ dài $n$ không có hai chữ số 1 liền nhau, tìm xâu thứ $k$. Gọi $f[\ell ]$ là số cách điền $\ell$ ô còn lại khi ô trước là 0 (được đặt tự do). Ta có $f[0]=1$, $f[1]=2$, $f[\ell ]=f[\ell -1]+f[\ell -2]$ (đặt 0 rồi điền tiếp $\ell -1$ ô, hoặc đặt 10 rồi điền tiếp $\ell -2$ ô): đúng dãy Fibonacci, với $n=1000$ thì cỡ ${10}^{209}$.

Chạy tay $n=5$, $k=7$. Bảng $f$ (hàng dưới minh họa khi chặn ở $\text{LIMIT}=10$ cho dễ thấy):

Dựng xâu từ trái sang. Tại mỗi vị trí, số xâu đặt 0 ở đây là $f[\text{còn lại}]$; nếu $k$ không vượt số đó thì đặt 0, ngược lại trừ đi và đặt 1:

vị trí  còn lại  số xâu đặt '0' ở đây   k    quyết định
0       4        f[4] = 8               7    7 <= 8  -> '0'
1       3        f[3] = 5               7    7 >  5  -> k = 2, '1'
2       2        f[2] = 3               2    2 <= 3  -> '0'  (sau '1' luôn vậy)
3       1        f[1] = 2               2    2 <= 2  -> '0'
4       0        f[0] = 1               2    2 >  1  -> k = 1, '1'

xâu thứ 7 = 01001

Liệt kê kiểm tra: 00000, 00001, 00010, 00100, 00101, 01000, 01001, ..., đúng xâu thứ $7$. Trong cả quá trình, giá trị bị chặn $f[5]=10$ chỉ được dùng ở bước kiểm tra "$k\le f[5]$" (có đủ $k$ xâu không), và vì $10\ge k$ nên kết quả kiểm tra không đổi. Mọi giá trị ta đem trừ khỏi $k$ đều nhỏ hơn $k$, nên đều chính xác.

Cài đặt

__int128: đọc, in, nhân modulo

__int128 là kiểu 128 bit có sẵn trong GCC/Clang khi biên dịch cho máy 64 bit, tức trên hầu hết online judge (trình biên dịch 64 bit), kể cả CTOJ. Trình biên dịch 32 bit (ví dụ GCC 32 bit trên Windows mà Codeforces từng dùng) không có kiểu này. Các phép + - * / % << >> và so sánh dùng như số thường, nhưng không có cin/cout/printf/to_string/stoll và không viết được hằng số vượt 64 bit trong mã nguồn. Tự viết đọc/in:

#include <bits/stdc++.h>
using namespace std;
typedef __int128 i128;
typedef unsigned long long ull;

// read a (possibly negative) integer that may not fit in long long
i128 readI128() {
    string s;
    cin >> s;
    bool neg = (s[0] == '-');
    i128 x = 0;  // accumulate as a non-positive value so -2^127 does not overflow
    for (size_t i = neg; i < s.size(); i++) x = x * 10 - (s[i] - '0');
    return neg ? x : -x;
}

string toString(i128 x) {
    if (x == 0) return "0";
    bool neg = x < 0;
    string s;
    while (x != 0) {
        int digit = (int)(x % 10);          // in [-9, 9] when x < 0
        s += char('0' + (digit < 0 ? -digit : digit));
        x /= 10;
    }
    if (neg) s += '-';
    reverse(s.begin(), s.end());
    return s;
}

// a * b mod m for a, b < m <= 2^63 without overflow
ull mulmod(ull a, ull b, ull m) {
    return (unsigned __int128)a * b % m;
}

ull powmod(ull a, ull e, ull m) {
    ull r = 1 % m;
    a %= m;
    for (; e > 0; e >>= 1) {
        if (e & 1) r = mulmod(r, a, m);
        a = mulmod(a, a, m);
    }
    return r;
}

int main() {
    i128 a = readI128(), b = readI128();
    cout << toString(a * b) << "\n";           // e.g. 10^18 * 10^18 = 10^36
    cout << powmod(2, 1000000, 1000000000000000003ULL) << "\n";
}

Cả hai hàm đều tránh đổi dấu giá trị nhỏ nhất $-2^{127}$ (đổi dấu giá trị này sẽ tràn, là hành vi không xác định): readI128 cộng dồn theo giá trị âm (x = x * 10 - digit) rồi mới đổi dấu khi số dương, còn toString lấy trị tuyệt đối từng chữ số thay vì đổi dấu cả số. mulmod là cách chuẩn để nhân modulo khi $m$ cỡ ${10}^{18}$, dùng trong Miller-Rabin và Pollard Rho hay băm với modulo $2^{61}-1$.

Số lớn cơ số ${10}^9$

Cấu trúc dưới đây chỉ làm việc với số không âm, đủ cho hầu hết bài đếm. Bất biến: không có khối $0$ ở đầu (số $0$ là mảng rỗng), nhờ đó so sánh được theo độ dài.

#include <bits/stdc++.h>
using namespace std;

// Non-negative big integer, base 1e9, little-endian: d[0] is the lowest block.
struct BigInt {
    static const int BASE = 1000000000;
    static const int WIDTH = 9;
    vector<int> d;  // invariant: no leading zero blocks; zero is {}

    BigInt(long long v = 0) {
        while (v > 0) { d.push_back(v % BASE); v /= BASE; }
    }
    explicit BigInt(const string& s) {
        // cut the decimal string into blocks of 9 digits from the right
        for (int end = (int)s.size(); end > 0; end -= WIDTH) {
            int start = max(0, end - WIDTH);
            d.push_back(stoi(s.substr(start, end - start)));
        }
        trim();
    }
    void trim() { while (!d.empty() && d.back() == 0) d.pop_back(); }
    bool isZero() const { return d.empty(); }

    string toString() const {
        if (d.empty()) return "0";
        string s = to_string(d.back());           // highest block: no padding
        for (int i = (int)d.size() - 2; i >= 0; i--) {
            string blk = to_string(d[i]);
            s += string(WIDTH - blk.size(), '0') + blk;  // pad inner blocks
        }
        return s;
    }
};

// -1 if a < b, 0 if equal, 1 if a > b
int cmp(const BigInt& a, const BigInt& b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1;
    for (int i = (int)a.d.size() - 1; i >= 0; i--)
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    return 0;
}

BigInt operator+(const BigInt& a, const BigInt& b) {
    BigInt c;
    int carry = 0;
    for (size_t i = 0; i < max(a.d.size(), b.d.size()) || carry; i++) {
        long long cur = carry;
        if (i < a.d.size()) cur += a.d[i];
        if (i < b.d.size()) cur += b.d[i];
        carry = cur >= BigInt::BASE;
        c.d.push_back(cur - (carry ? BigInt::BASE : 0));
    }
    return c;
}

// requires a >= b
BigInt operator-(const BigInt& a, const BigInt& b) {
    BigInt c = a;
    int borrow = 0;
    for (size_t i = 0; i < c.d.size(); i++) {
        long long cur = (long long)c.d[i] - borrow - (i < b.d.size() ? b.d[i] : 0);
        borrow = cur < 0;
        if (borrow) cur += BigInt::BASE;
        c.d[i] = (int)cur;
    }
    c.trim();
    return c;
}

// multiply by a small number 0 <= m < 2^63 / BASE (about 9.2e9)
BigInt mulSmall(const BigInt& a, long long m) {
    if (m == 0 || a.isZero()) return BigInt();
    BigInt c;
    long long carry = 0;
    for (size_t i = 0; i < a.d.size() || carry; i++) {
        long long cur = carry + (i < a.d.size() ? a.d[i] * m : 0);
        c.d.push_back(cur % BigInt::BASE);
        carry = cur / BigInt::BASE;
    }
    return c;
}

// schoolbook multiplication, O(n * m) blocks
BigInt operator*(const BigInt& a, const BigInt& b) {
    if (a.isZero() || b.isZero()) return BigInt();
    vector<unsigned long long> t(a.d.size() + b.d.size(), 0);
    for (size_t i = 0; i < a.d.size(); i++) {
        unsigned long long carry = 0;
        for (size_t j = 0; j < b.d.size() || carry; j++) {
            unsigned long long cur = t[i + j] + carry
                + (j < b.d.size() ? (unsigned long long)a.d[i] * b.d[j] : 0);
            t[i + j] = cur % BigInt::BASE;   // keep each cell below BASE
            carry = cur / BigInt::BASE;
        }
    }
    BigInt c;
    c.d.assign(t.begin(), t.end());
    c.trim();
    return c;
}

// divide by a small positive number, returns quotient; remainder goes to rem
BigInt divSmall(const BigInt& a, long long m, long long& rem) {
    BigInt q;
    q.d.assign(a.d.size(), 0);
    rem = 0;
    for (int i = (int)a.d.size() - 1; i >= 0; i--) {   // from the highest block
        long long cur = rem * BigInt::BASE + a.d[i];
        q.d[i] = (int)(cur / m);
        rem = cur % m;
    }
    q.trim();
    return q;
}

int main() {
    // 30! exactly
    BigInt f(1);
    for (int i = 2; i <= 30; i++) f = mulSmall(f, i);
    cout << f.toString() << "\n";      // 265252859812191058636308480000000

    // C(100, 50) exactly: after step i the value is C(50 + i, i), so each division is exact
    BigInt c(1);
    for (int i = 1; i <= 50; i++) {
        long long r;
        c = divSmall(mulSmall(c, 50 + i), i, r);
    }
    cout << c.toString() << "\n";      // 100891344545564193334812497256

    BigInt x("123456789012345678901"), y("98765432109876543210");
    cout << (x + y).toString() << " " << (x - y).toString() << " "
         << (x * y).toString() << " " << cmp(x, y) << "\n";
}

Một vài điểm then chốt:

• Trong phép nhân hai số lớn, ô t[i + j] luôn được đưa về dưới ${10}^9$ ngay sau mỗi lần cộng, số nhớ chuyển sang ô kế tiếp. Nhờ vậy cur $\le ({10}^9-1)+({10}^9-1{)}^2+\text{nhớ}<1,1·{10}^{18}$, luôn vừa unsigned long long.
• divSmall cần rem * BASE + d[i] vừa long long, tức $m\lesssim 9·{10}^9$. Tương tự mulSmall cần $d_i·m+\text{nhớ}<9,2·{10}^{18}$.
• Tính $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ chính xác theo công thức nhân dần (như main ở trên) chỉ cần mulSmall và divSmall, và phép chia luôn hết vì sau bước $i$ giá trị đúng bằng $\left(\genfrac{}{}{0ex}{}{n-k+i}{i}\right)$. Cách khác là dựng tam giác Pascal bằng phép cộng số lớn. Xem thêm tổ hợp.
• Cần số âm thì lưu thêm một cờ dấu: cộng hai số cùng dấu là cộng trị tuyệt đối; khác dấu thì so sánh trị tuyệt đối rồi lấy lớn trừ nhỏ.

Chặn trên (saturating arithmetic)

Code bài "xâu nhị phân thứ $k$" ở trên, với $n\le {10}^5$ và $k\le {10}^{18}$:

#include <bits/stdc++.h>
using namespace std;

const long long LIMIT = (long long)2e18;   // any value > max k works

// general helpers: operands are in [0, LIMIT]
long long satAdd(long long a, long long b) { return min(LIMIT, a + b); }
long long satMul(long long a, long long b) {
    if (a != 0 && b > LIMIT / a) return LIMIT;   // check before multiplying
    return min(LIMIT, a * b);
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    // f[len][prev] = number of ways to fill len more positions, previous char = prev
    vector<array<long long, 2>> f(n + 1);
    f[0] = {1, 1};
    for (int len = 1; len <= n; len++) {
        f[len][0] = satAdd(f[len - 1][0], f[len - 1][1]);  // put '0' or '1'
        f[len][1] = f[len - 1][0];                         // must put '0'
    }
    if (k > f[n][0]) { cout << -1 << "\n"; return 0; }   // fewer than k strings
    string s;
    for (int pos = 0; pos < n; pos++) {
        int rem = n - pos - 1;
        long long withZero = f[rem][0];      // strings that put '0' here
        if (k <= withZero) s += '0';
        else { k -= withZero; s += '1'; }    // withZero < k, so it is exact
        // after a '1', k <= f[rem][1] == f[rem-1][0], so the next step always picks '0'
    }
    cout << s << "\n";
}

Cùng bài này mà không chặn, ô $f[\ell ]$ chứa số Fibonacci $F_{\ell +2}$ nên độ dài tăng dần theo $\ell$, các ô cuối bảng chứa số tới khoảng $20900$ chữ số (cả bảng cộng lại cỡ ${10}^9$ chữ số): vừa tốn bộ nhớ vừa chậm hơn hàng nghìn lần.

Python: số nguyên không giới hạn

Trong Python, int tự mở rộng, nên mọi phép tính trên đều "miễn phí" về mặt code:

import sys
from math import comb, factorial
# allow printing ints longer than 4300 digits (the function is missing on old unpatched Pythons)
if hasattr(sys, 'set_int_max_str_digits'):
    sys.set_int_max_str_digits(0)

x = 123456789012345678901
y = 98765432109876543210
print(x + y, x - y, x * y)        # exact
print(x // 37, x % 37)            # floor division and remainder
print(comb(100, 50))              # 100891344545564193334812497256
print(pow(2, 10**6, 10**18 + 3))  # modular power, no overflow worries
print(len(str(factorial(10**5)))) # 456574 digits, computed in C code: fast

Python không thay thế được mọi thứ. Mỗi phép toán trên số lớn tốn thời gian tỉ lệ với độ dài số, và vòng lặp Python vốn chậm hơn C++ nhiều lần:

• Nhân tích lũy $1·2\cdots {10}^5$ bằng vòng for mất khoảng $3,6$ giây vì mỗi bước nhân một số hàng trăm nghìn chữ số, trong khi math.factorial(10**5) chỉ khoảng $0,14$ giây (thuật toán chia để trị viết bằng C).
• DP có ${10}^6$ trạng thái mà mỗi trạng thái cộng số lớn vài trăm chữ số là quá chậm. Khi đó hãy nghĩ tới chặn trên, hoặc __int128 nếu đáp án $<{10}^{38}$.
• Ở Python 3.11 trở về trước, đổi số rất dài sang xâu (str, print) tốn thời gian bình phương theo số chữ số. Từ Python 3.12, việc đổi này dùng thuật toán dưới bình phương cho số rất lớn: str() một số $456574$ chữ số trên Python 3.13 chỉ mất khoảng $0,08$ giây.
• Từ Python 3.11 (và các bản vá 3.10.7, 3.9.14, 3.8.14), đổi số hơn $4300$ chữ số sang xâu bị chặn theo mặc định: phải gọi sys.set_int_max_str_digits(0). Trên bản cũ chưa có bản vá thì hàm này không tồn tại (gọi thẳng sẽ ném AttributeError), nên bọc bằng if hasattr(sys, 'set_int_max_str_digits') như code trên.

Xem thêm các mẹo tăng tốc ở Python cho thi đấu.

Độ phức tạp

Gọi $n,m$ là số khối (bằng số chữ số chia $9$) của hai toán hạng.

Bộ nhớ: một số $L$ chữ số cần $\lceil L/9\rceil$ số int. Bảng DP chứa số lớn tốn (số trạng thái) $\times$ (số khối), đây thường là giới hạn thật sự: ${10}^4$ trạng thái mỗi trạng thái $1000$ chữ số đã là khoảng $4,5$ MB.

Cẩn thận với vòng lặp tích lũy: nhân dồn $n!$ bằng mulSmall cho $i=2..n$ tốn ${\sum }_i(\text{số khối của }i!)=O(n·\frac{{\log }_{10}n!}{9})$, tức gần $O(n^2\log n)$ chứ không phải $O(n)$. Với $n={10}^5$ là cỡ $2,5·{10}^9$ phép tính khối: quá chậm. Nhân hai số lớn cỡ ${10}^5$ chữ số bằng $O(nm)$ cũng quá chậm, lúc đó cần Karatsuba hoặc FFT.

⚠️ Lỗi thường gặp

• Tràn trước khi gán: long long x = a * b; với a, b kiểu int vẫn tràn, vì phép nhân thực hiện trên int rồi mới đổi kiểu. Viết 1LL * a * b. Tương tự 1 << 40 là int, phải viết 1LL << 40.
• Kiểm tra tràn sau khi đã tràn: if (a * b < 0) hay if (a * b / b != a) với số có dấu là hành vi không xác định, trình biên dịch với -O2 có quyền xóa luôn phép kiểm tra. Hãy kiểm tra trước (a > LIMIT / b), hoặc dùng __builtin_mul_overflow(a, b, &res). Chỉ số không dấu mới tràn "vòng" theo modulo $2^{64}$ một cách hợp lệ.
• Tin double hoặc pow: double chỉ chính xác tới $2^{53}\approx 9·{10}^{15}$. Ví dụ (long long)sqrt((double)999999999999999999LL) ra ${10}^9$ (vì ${10}^{18}-1$ bị làm tròn thành ${10}^{18}$) trong khi đáp số đúng là $999999999$; (long long)pow(3, 38) ra 1350851717672992000 thay vì $3^{38}=1350851717672992089$. Hai tích khác nhau cỡ ${10}^{18}$ có thể thành cùng một double. Dùng số nguyên, và nếu lấy căn thì chỉnh lại bằng vòng while.
• Quên đệm số 0 khi in số lớn: in d[i] bằng cout << d[i] cho các khối giữa làm mất chữ số 0 đầu khối. Chỉ khối cao nhất in trơn, các khối còn lại in đủ $9$ chữ số (printf("%09d", d[i])).
• Để lại khối 0 ở đầu: sau phép trừ hoặc chia, nếu không trim() thì hàm so sánh theo độ dài sai (coi [5, 0] lớn hơn [7]) và in ra số 0 thừa. Phép trừ không dấu cũng phải đảm bảo $a\ge b$, so sánh trước khi trừ.
• Tích lũy tích rồi mới xử lý nhớ: cộng dồn mọi $a_i{b}_j$ vào ô t[i + j] rồi cuối cùng mới chuẩn hóa sẽ tràn unsigned long long khi có nhiều hơn khoảng $18$ tích chồng lên một ô. Phải đưa ô về dưới ${10}^9$ sau mỗi lần cộng như code mẫu.
• Chặn trên sai cách: $\text{LIMIT}$ phải lớn hơn mọi giá trị đem ra so sánh (thường $>{10}^{18}$), và $2·\text{LIMIT}$ không được tràn (chọn $2·{10}^{18}$, đừng chọn LLONG_MAX). Không bao giờ trừ hay chia một giá trị có thể đã bị chặn: chỉ trừ khi chắc nó nhỏ hơn ngưỡng. Và nhân phải kiểm tra trước, không phải min(LIMIT, a * b) khi a * b đã tràn.
• Nhầm phạm vi __int128: nó chỉ tới khoảng $1,7·{10}^{38}$, tức $33!$ hay $\left(\genfrac{}{}{0ex}{}{130}{65}\right)$. Đáp án $199!$ (khoảng $373$ chữ số) vẫn cần số lớn thật. __int128 cũng không đọc/in được bằng cin/cout, không có to_string, đừng trông cậy vào std::abs, và hằng số lớn phải dựng bằng dịch bit ((__int128)1 << 100) hoặc đọc từ xâu.
• Đọc số lớn bằng long long: nếu đề cho $k$ hoặc $t$ tới ${10}^{30}$, cin >> long long sẽ thất bại lặng lẽ. Đọc thành string rồi chuyển sang __int128 hoặc số lớn.
• Python bị giới hạn chữ số khi in: từ Python 3.11 (và các bản vá 3.10.7, 3.9.14, 3.8.14), print một số hơn $4300$ chữ số ném ValueError. Gọi sys.set_int_max_str_digits(0) ở đầu chương trình, bọc trong if hasattr(sys, 'set_int_max_str_digits') để không lỗi AttributeError trên Python cũ.

Biến thể / Mở rộng

• Tính theo modulo $2^{64}$ (hoặc $2^{128}$) khi đề bảo đảm đáp án nhỏ: phép cộng, trừ, nhân trên unsigned long long tự lấy modulo $2^{64}$. Nếu đề bảo đảm đáp án cuối $<2^{64}$ (hoặc $<2^{128}$ với unsigned __int128) thì có thể để giá trị trung gian tràn thoải mái, kể cả khi có phép trừ, và kết quả cuối vẫn đúng. Mẹo này không dùng được nếu có phép chia hay so sánh trên giá trị trung gian.
• Định lý phần dư Trung Hoa: tính đáp án theo vài modulo nguyên tố khoảng ${10}^9$ rồi ghép lại (CRT) để khôi phục một số lớn đã biết cận trên. Hữu ích khi phép toán chính là nhân ma trận hay đa thức mà cài số lớn trực tiếp thì quá chậm.
• Nhân nhanh: Karatsuba $O(n^{1,585})$ hoặc nhân đa thức bằng FFT $O(n\log n)$ khi hai số dài hàng trăm nghìn chữ số.
• So sánh qua logarit: khi chỉ cần biết tích nào lớn hơn (không cần giá trị), so sánh $\sum \log a_i$ bằng long double. Cách này có sai số, chỉ dùng khi hai vế chênh nhau rõ rệt hoặc đề cho phép.
• Liên hệ: số lớn và chặn trên xuất hiện dày đặc trong tổ hợp (tính $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ chính xác), hạng của hoán vị và quy hoạch động chữ số (đếm rồi dựng phần tử thứ $k$). Khi đề cho modulo thì hãy dùng số học modulo thay vì số lớn, xem định lý Lucas. Ước lượng độ lớn là một phần của ước lượng giới hạn.

Bài tập luyện

Luyện kỹ thuật

• Nhân 17 (times17) (Sơ cấp) nhân một số nhị phân tới $1000$ chữ số với $17$: đúng phép "nhân với số nhỏ" nhưng trong cơ số $2$ (hoặc cộng $N$ với $N$ dịch trái $4$ bit).
• Lãi Suất Goblin (gobint) (Học việc) đáp án không quá ${10}^{18}$ nhưng giá trị trung gian $P·(100+R{)}^Y$ thì khổng lồ: nhân số lớn với số nhỏ $Y$ lần rồi chia cho ${100}^Y$, không dùng double.
• Petya và Java (petyajava) (Trung cấp) đọc số tới $100$ chữ số dưới dạng xâu và so sánh với các ngưỡng byte, short, int, long: luyện phép so sánh số lớn (theo độ dài, rồi theo từ điển).
• Luỹ thừa của k trong đoạn (kpowers) (Trung cấp) nhân dần $k^i$ khi $r\le {10}^{18}$, $k\le {10}^9$: phép nhân kế tiếp có thể tới ${10}^{27}$, phải kiểm tra cur > r / k trước khi nhân hoặc dùng __int128.
• Chuyến du hành vũ trụ (spacevoy) (Nâng cao) tìm kiếm nhị phân trên $x$ tới cỡ ${10}^{18}$, mỗi bước tính $\sum \lfloor a_{i}x/b_i\rfloor$ với tích tới ${10}^{27}$: dùng __int128 hoặc chặn trên tổng vì chỉ cần so sánh với $c$.

Đề VOI

• Siêu thị may mắn (voi07_market) (Nâng cao) VOI 2007: DP cái túi đếm số cách có đáp án vượt $2^{64}$ nhưng dưới ${10}^{38}$, nên để mọi phép cộng trừ tự tràn vòng theo modulo $2^{128}$ bằng unsigned __int128 rồi tự viết hàm in ra thập phân.
• Quà tết (voi08_gifts) (Kỳ cựu) VOI 2008: phần chính là theo dõi vị trí một ô qua các lần gấp, nhưng số thứ tự cần in có thể tới $4^{40}=2^{80}$ nên phải dùng số nguyên 128 bit (hoặc số lớn) thay cho long long.
• Sản xuất đồ chơi (voi13_organ) (Kỳ cựu) VOI 2013: đáp án có thể lớn cỡ $199!$ (hàng trăm chữ số), nên bảng đếm và DP lấy max phải chạy trên số lớn cơ số ${10}^9$ với phép cộng, nhân số nhỏ và so sánh; subtask nhỏ vừa long long hay __int128.
• Chất lượng dịch vụ (voi14_qos) (Kỳ cựu) VOI 2014: số đường đi thỏa điều kiện tăng theo hàm mũ nhưng chỉ dùng để so sánh với $k$ khi dựng đường thứ $k$, nên chặn trên mọi số đếm.
• Tạo đề thi (voi16_exam) (Kỳ cựu) VOI 2016: giá trị một cách đặt ngoặc có thể tới ${10}^{24}$ và hai giá trị khác nhau phải được phân biệt chính xác, nên hãy tính và so sánh chúng bằng __int128 chứ không phải long long hay double.
• Xâu đối xứng (voi17_qpalin) (Kỳ cựu) VOI 2017: bài "đếm rồi dựng phần tử thứ $t$" với số lượng xâu tới $5^{50}\approx 8,9·{10}^{34}$, vượt 64 bit nhưng vẫn vừa __int128; nhớ đọc $t$ dưới dạng xâu.
• Bài tập đêm giáng sinh (voi24_noel) (Chuyên gia) VOI 2024: số cách phân đoạn tăng ít nhất như dãy Fibonacci nên vượt ${10}^{17}$ rất nhanh; hãy tìm xem vùng nào thật sự cần số đếm chính xác (bằng __int128), phần còn lại chỉ cần biết "đủ lớn".