C++中如何存储2^1000000量级变量与字符串？求2^1000000末三位解法

一、快速求2^n的最后三位数字（无需存储完整大数） #

你遇到的数值溢出问题其实完全可以避免——因为我们只需要最后三位，利用模运算的性质就能高效计算：

对于整数a、b和模数m，有 (a * b) % m = [(a % m) * (b % m)] % m

所以计算2^n mod 1000时，每一步只需要保留当前结果的最后三位，再乘2取模即可，这样数值永远不会超过1000，完全不会溢出。

方法1：循环迭代（简单直观） #

#include <iostream>
using namespace std;

int main() {
    long long n = 1000000;
    int result = 1; // 2^0 = 1
    for (long long i = 0; i < n; ++i) {
        result = (result * 2) % 1000;
    }
    cout << "最后三位数字：" << result << endl;
    return 0;
}

这个方法时间复杂度是O(n)，n=1e6完全没问题，运行瞬间完成。

方法2：快速幂算法（更高效，适合极大n） #

如果n大到离谱（比如1e18），可以用快速幂把时间复杂度降到O(log n)：

#include <iostream>
using namespace std;

long long fast_pow_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    long long n = 1000000;
    long long last_three = fast_pow_mod(2, n, 1000);
    cout << "最后三位数字：" << last_three << endl;
    return 0;
}

二、C++中存储2^1000000量级的超大数 #

2^1000000大约有301030位，远超C++原生数值类型（比如unsigned long long最多存19位），所以需要用以下两种方式处理：

1. 手动用字符串实现大整数 #

自己写逻辑把数字存在字符串里，实现乘法、加法等操作。比如计算2^1000000的完整值：

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string multiply_by_two(string num) {
    string result;
    int carry = 0;
    // 从后往前遍历每一位
    for (int i = num.size() - 1; i >= 0; --i) {
        int digit = num[i] - '0';
        int product = digit * 2 + carry;
        result.push_back((product % 10) + '0');
        carry = product / 10;
    }
    // 处理剩余的进位
    while (carry > 0) {
        result.push_back((carry % 10) + '0');
        carry /= 10;
    }
    // 反转得到正确顺序
    reverse(result.begin(), result.end());
    return result;
}

int main() {
    string num = "1"; // 初始是2^0
    long long n = 1000000;
    for (long long i = 0; i < n; ++i) {
        num = multiply_by_two(num);
    }
    // 可以输出前几位或后几位，完整输出会很长
    cout << "2^1000000的前10位：" << num.substr(0, 10) << endl;
    cout << "2^1000000的后3位：" << num.substr(num.size() - 3, 3) << endl;
    return 0;
}

这个方法需要自己实现大整数运算，适合理解底层逻辑，但效率不如成熟库。

2. 使用第三方大整数库 #

如果不想重复造轮子，可以用现成的库：

• GMP（GNU Multiple Precision Arithmetic Library）：专门处理超大整数，支持各种运算，C++中可以通过gmpxx.h调用。
• Boost.Multiprecision：Boost库的一部分，提供cpp_int类型，可以直接像原生整数一样操作，非常方便。

比如用Boost.Multiprecision的示例：

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

int main() {
    cpp_int num = 1;
    long long n = 1000000;
    for (long long i = 0; i < n; ++i) {
        num *= 2;
    }
    cout << "2^1000000的后3位：" << num % 1000 << endl;
    return 0;
}

注意使用这些库需要提前安装并在编译时链接对应的库文件（比如GMP需要加-lgmp -lgmpxx）。

内容的提问来源于stack exchange，提问作者slicebattle