Как получить результат 2 ^ 100 * 3 ^ 3 по модулю 1000000007 - PullRequest
Новая
       15

Как получить результат 2 ^ 100 * 3 ^ 3 по модулю 1000000007

0 голосов
/ 03 ноября 2019

У меня вопрос, как получить результат (2 ^ 100) * (3 ^ 5) по модулю 10 ^ 9 + 7? Программа попросит пользователя ввести мощность (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 вывод.

1 Ответ

2 голосов
/ 03 ноября 2019

Во-первых, 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;
}

Обратите внимание, что это все еще неоптимально - можно рассчитать гораздо большие степени, используя возведение в степень путем возведения в квадрат .

Наконец вы должны заметить, что последний продукт должен быть также мод 1000000007, в противном случае результат будет больше, чем ожидалось: 

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