C++中如何计算大数幂的模？解决m*10^n mod 1e9+7溢出问题

Great question! Let's break this down into two clear parts: first, the general approach to computing large exponentiation modulo a number in C++, and second, how to efficiently handle your specific problem where the result takes the form m * 10^n with an extremely large exponent n (up to 10^18).

The key to computing base^exp mod mod_value without overflow is using the fast power (exponentiation by squaring) technique. This method cuts the time complexity from O(exp) to O(log exp) by breaking the exponent into its binary representation—we square the base repeatedly and multiply it into the result only when the corresponding bit in the exponent is set. Every multiplication step takes the modulo to keep intermediate values within bounds.

Here's a clean C++ implementation of the fast power function:

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    // Ensure the base starts within the modulo range
    base = base % mod;
    
    while (exp > 0) {
        // If the current exponent bit is set, multiply base into the result
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        // Square the base and halve the exponent (bit shift is efficient)
        exp = exp >> 1; // Equivalent to exp /= 2
        base = (base * base) % mod;
    }
    return result;
}

Since your answer is always m * 10^n where 1 ≤ m ≤ 8 and 2 ≤ n ≤ 10^18, we can leverage modulo arithmetic properties to simplify this:

• By the rule of modulo multiplication: (a * b) mod MOD = [(a mod MOD) * (b mod MOD)] mod MOD
• m mod MOD is just m (since m ≤ 8 < 1e9+7)
• We only need to compute 10^n mod MOD with the fast power function, then multiply by m and take modulo MOD again.

Here's a complete example tailored to your problem:

#include <iostream>
using namespace std;

const long long MOD = 1000000007;

long long mod_pow(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;
        }
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int main() {
    int m;
    long long n; // Use long long to store n—10^18 is way beyond 32-bit integer limits
    cin >> m >> n;
    
    long long power_of_10 = mod_pow(10, n, MOD);
    // 1LL * m ensures we use 64-bit multiplication to avoid overflow
    long long answer = (1LL * m * power_of_10) % MOD;
    
    cout << answer << endl;
    return 0;
}

Quick Notes: #

• Always use long long for n—a 32-bit integer can only hold up to ~2e9, which is nowhere near 10^18.
• The 1LL * m trick ensures the multiplication happens in 64-bit space, preventing overflow even if m were larger (though your m ≤8 makes this extra safe).
• The fast power function handles n=1e18 easily—it only takes around 60 iterations (since log2(1e18) ≈ 60).

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