c - 如何以 1000000007 为模得到结果 2^100 * 3^3

问题描述

我有一个问题，如何在模 10^9 + 7 中得到 (2^100)*(3^5) 的结果？程序会要求用户输入功率 (2^a) 和 3^b，然后输出将显示 2^a * 3^b 的结果。

我试图将所有大数转换为模数，并乘以模数。但是，它不适用于 2*100 * 3^5

#include "stdio.h"

int main()
{
    long long int testcase,b,c,N,a;
    long long int pow2,pow3 = 1;
    long long int m = 1000000007;

    // input the power
    scanf("%lld",&a); getchar();
    scanf("%lld",&b); getchar();

    // power of 2 (2^a)
    for(int i = 1; i <= a; i++){
        pow2 = pow2 * 2;
    }
    // power of 3 (3^b)
    for(int j = 1; j <= b; j++){
        pow3 = pow3 * 3;
    }

    // convert the big numbers into modulo
    long long int i = 1;
    i = (1*pow2) % m ;
    long long int j = 1;
    j = (1*pow3) % m;

    // the result of first modulo times second modulo
    printf("%lld\n", i*j);
    // doesnt work for 2^100 * 3^5

    return 0;
}

对于 a = 2 和 b = 5，它给出 972 的输出（这是正确的），对于 a = 100 和 b = 3，它给出 0 输出。

标签： cmodulo

首先，pow2未初始化，因此行为未定义。如果初始化为1，那么问题是 2^100 不适合long long int. 最好的解决方法是尽可能多地取模。

// power of 2 (2^a)
for(int i = 1; i <= a; i++){
    pow2 *= 2;
    pow2 %= m;
}
// power of 3 (3^b)
for(int j = 1; j <= b; j++){
    pow3 *= 3;
    pow3 %= m;
}

请注意，这仍然不是最理想的 - 可以通过使用平方乘幂来计算更大的幂。

最后你必须注意最后一个产品也必须是 mod 1000000007，否则结果比预期的要大：

printf("%lld\n", i * j % m);

c - 如何以 1000000007 为模得到结果 2^100 * 3^3

问题描述

解决方案

推荐阅读