__int128 基础与使用

一、为什么需要 __int128

在 C++ 竞赛代码中，我们最常用的大整数类型通常是 long long。它的范围大约是：

$$-9\times 10^{18}\sim 9\times 10^{18}$$

更准确地说，long long 最大值是：

$$9223372036854775807$$

这个范围在很多题目中已经够用了。例如数组元素在 $10^9$ 以内，求和次数在 $10^5$ 以内，总和大约是 $10^{14}$，用 long long 完全没有问题。

但是有些题目的数据范围会更大。

比如某些题中：

$$N\le 10^{18}$$

每次贡献最大为：

$$10^9$$

那么总答案可能达到：

$$10^{18}\times 10^9=10^{27}$$

这个数远远超过了 long long 的范围。

如果仍然使用 long long，程序不会报错，但结果会发生溢出，得到一个完全错误的数。这个错误非常隐蔽，因为程序能够正常编译，也能够正常运行，只是答案不对。

这时就需要使用更大的整数类型：

__int128

__int128 可以理解成一个更大的整数类型，范围大约能达到：

$$10^{38}$$

所以它可以轻松存下 $10^{27}$ 级别的答案。

需要注意的是，__int128 不是标准 C++ 类型，而是 GCC 和 Clang 支持的扩展类型。在大多数使用 GNU C++14、GNU C++17 的 OJ 中都可以使用。

二、__int128 的基本写法

__int128 的名字比较长，实际写代码时通常会起一个别名：

using i128 = __int128;

之后就可以像使用普通整数一样使用它：

i128 x = 0;
i128 y = 100;
i128 z = x + y;

例如：

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

using i128 = __int128;

int main() {
    i128 x = 100;
    i128 y = 200;
    i128 z = x + y;

    return 0;
}

不过 __int128 最常见的用法不是直接存很大的输入，而是用来承接计算中的大结果。

比如：

long long a = 1000000000000000000LL;
long long b = 1000000000LL;

i128 c = (i128)a * b;

这里：

$$a=10^{18}$$ $$b=10^9$$

所以：

$$c=10^{27}$$

这个结果 long long 存不下，但 __int128 可以存下。

这里有一个非常重要的细节：乘法前必须把其中一个数强制转换成 __int128。

正确写法是：

i128 c = (i128)a * b;

不推荐写成：

i128 c = a * b;

因为 a 和 b 都是 long long，右边的 a * b 会先按照 long long 计算。计算过程中可能已经溢出了，最后再赋值给 __int128 已经来不及了。

所以，只要两个 long long 相乘可能爆范围，就要提前转成 __int128：

i128 res = (i128)x * y;

这是使用 __int128 时最重要的习惯之一。

三、__int128 的输入与输出

__int128 可以参与加减乘除和取模运算，但它不能直接使用 cin 和 cout。

下面这种写法是错误的：

__int128 x;
cin >> x;
cout << x;

大多数题目中，输入数据本身通常不会超过 long long，只是计算结果可能超过 long long。

这种情况下，可以先用 long long 读入，再在计算时转成 __int128：

long long a, b;
cin >> a >> b;

i128 ans = (i128)a * b;

但是输出 __int128 需要自己写函数。

输出函数的思路和手写高精度转字符串很像：不断取最后一位数字，然后倒序输出。

using i128 = __int128;

void put(i128 x) {
    if(x == 0) {
        cout << 0;
        return;
    }

    if(x < 0) {
        cout << '-';
        x = -x;
    }

    string s;

    while(x) {
        s += char(x % 10 + '0');
        x /= 10;
    }

    reverse(s.begin(), s.end());

    cout << s;
}

完整示例：

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

using i128 = __int128;

void put(i128 x) {
    if(x == 0) {
        cout << 0;
        return;
    }

    if(x < 0) {
        cout << '-';
        x = -x;
    }

    string s;

    while(x) {
        s += char(x % 10 + '0');
        x /= 10;
    }

    reverse(s.begin(), s.end());

    cout << s;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    long long a, b;
    cin >> a >> b;

    i128 ans = (i128)a * b;

    put(ans);

    return 0;
}

如果输入：

1000000000000000000 1000000000

程序会输出：

1000000000000000000000000000

也就是：

$$10^{27}$$

如果输入本身也可能超过 long long，就需要手写读入函数。

using i128 = __int128;

i128 read() {
    string s;
    cin >> s;

    i128 x = 0;
    int p = 0;
    int f = 1;

    if(s[0] == '-') {
        f = -1;
        p = 1;
    }

    for(int i = p; i < (int)s.size(); i++) {
        x = x * 10 + s[i] - '0';
    }

    return x * f;
}

不过在大多数算法题里，通常只需要手写输出，不需要手写读入。

四、__int128 的常见使用场景

第一类场景是两个大数相乘。

比如：

$$a,b\le 10^{18}$$

如果要计算：

$$a\times b$$

那么最大可能达到：

$$10^{36}$$

这个结果一定会超过 long long。

即使最后要对某个数取模，中间乘法也可能先溢出。

例如：

long long a, b, mod;
cin >> a >> b >> mod;

long long ans = a * b % mod;

如果 $a,b$ 都接近 $10^{18}$，那么 a * b 会先溢出，再取模，结果是错的。

正确写法是：

long long ans = (__int128)a * b % mod;

可以封装成函数：

long long mul(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}

第二类场景是答案总和可能很大。

比如一个过程执行 $N$ 次，每次最多增加 $a$，其中：

$$N\le 10^{18}$$ $$a\le 10^9$$

那么答案可能是：

$$10^{27}$$

这时就不能用 long long 存答案。

例如：

long long n, a;
cin >> n >> a;

i128 ans = (i128)n * a;
put(ans);

第三类场景是矩阵快速幂、DP 转移等问题中，单步贡献不大，但步数极大。

例如某个 DP 每一步最多增加 $10^9$，但一共可能转移 $10^{18}$ 步，那么最终答案也可能达到 $10^{27}$。

这种情况下，矩阵元素、DP 状态、最终答案都应该使用 __int128。

例如：

using i128 = __int128;

struct Mat {
    i128 a[2][2];
};

第四类场景是比较大小时避免乘法溢出。

有时不一定需要真的得到乘积，只是要比较：

$$a\times b \le c$$

如果直接写：

if(a * b <= c)

可能 a * b 已经溢出。

可以改成：

if((i128)a * b <= c)

这样比较才是安全的。

五、__int128 和取模运算

在取模题中，__int128 最常见的作用是防止乘法中间结果溢出。

比如普通快速幂中，如果 $mod$ 不大，例如 $10^9+7$，那么：

$$a\times a$$

大约不会超过 $10^{18}$，还在 long long 范围内。

但是如果 $mod$ 接近 $10^{18}$，那么：

$$a\times a$$

可能达到：

$$10^{36}$$

这就会爆 long long。

此时可以把快速幂中的乘法改成 __int128：

using ll = long long;

ll mul(ll a, ll b, ll mod) {
    return (__int128)a * b % mod;
}

ll qpow(ll a, ll b, ll mod) {
    ll res = 1 % mod;

    while(b) {
        if(b & 1) {
            res = mul(res, a, mod);
        }

        a = mul(a, a, mod);
        b >>= 1;
    }

    return res;
}

这样即使 $mod$ 接近 $10^{18}$，乘法中间结果也不会在 long long 里溢出。

这里要注意，__int128 只是解决了中间乘法溢出的问题。如果最终答案本身需要在模意义下输出，那么返回 long long 是可以的，因为最终结果一定小于 mod。

但是如果题目要求输出完整答案，不取模，而且答案超过 long long，那就必须用 __int128 存答案，并用 put 函数输出。

六、__int128 的完整模板

下面是一个比较常用的 __int128 模板，包含读入、输出和乘法取模。

如果题目输入不会超过 long long，可以只保留 put 函数。

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

using ll = long long;
using i128 = __int128;

i128 read() {
    string s;
    cin >> s;

    i128 x = 0;
    int p = 0;
    int f = 1;

    if(s[0] == '-') {
        f = -1;
        p = 1;
    }

    for(int i = p; i < (int)s.size(); i++) {
        x = x * 10 + s[i] - '0';
    }

    return x * f;
}

void put(i128 x) {
    if(x == 0) {
        cout << 0;
        return;
    }

    if(x < 0) {
        cout << '-';
        x = -x;
    }

    string s;

    while(x) {
        s += char(x % 10 + '0');
        x /= 10;
    }

    reverse(s.begin(), s.end());

    cout << s;
}

ll mul(ll a, ll b, ll mod) {
    return (i128)a * b % mod;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll a, b;
    cin >> a >> b;

    i128 ans = (i128)a * b;

    put(ans);

    return 0;
}

在实际比赛中，不需要每次都把整个模板复制进去。可以根据题目需要选择：

如果只是答案超过 long long，保留 using i128 = __int128; 和 put。

如果输入也超过 long long，再加上 read。

如果只是取模乘法溢出，保留 mul 函数即可。

七、使用 __int128 时的注意事项

第一，不能直接用 cout 输出。

错误写法：

i128 x = 100;
cout << x;

正确写法：

put(x);

第二，乘法前要提前转换类型。

错误写法：

i128 c = a * b;

如果 a 和 b 都是 long long，右边会先按 long long 计算，可能已经溢出。

正确写法：

i128 c = (i128)a * b;

第三，不要滥用 __int128。

如果 long long 足够，就没有必要全部写成 __int128。__int128 虽然好用，但输出麻烦，而且不是标准 C++ 类型。

一般建议：

输入数据在 long long 范围内，就用 long long 读入。

中间计算可能爆 long long，再局部转成 __int128。

最终答案超过 long long，再用 __int128 保存并手写输出。

第四，要确认 OJ 编译环境是否支持。

__int128 是 GNU 扩展类型，通常在 GNU C++14、GNU C++17、GNU C++20 下可以使用。如果编译器是 MSVC，或者题目要求严格标准 C++，可能无法使用。

第五，__int128 不是高精度。

它只是比 long long 更大的整数类型，并不是无限大。

如果答案超过 $10^{38}$，__int128 也会溢出。这时就需要真正的高精度整数，例如用字符串、数组，或者使用支持大整数的语言和库。

__int128 的定位可以理解为：它适合处理中等程度的大整数，尤其适合解决 long long 不够、但又不需要完整高精度的问题。