Как вычислить остаток от а в степени b разделить на десять в степени девять плюс семь
Я написал код для вычисления a в степени b, а затем вычисления pow(a,b) % 1000000007
1000000007 = pow(10,9) + 7
a и b — целые числа в диапазоне 1 <= a,b <= 10000000
очевидно, pow(a,b) - очень большое число, поэтому я думаю, что в моем коде происходит переполнение. как я могу оптимизировать и исправить свой код?
#include <stdio.h>
#include <math.h>
unsigned long long int power(unsigned long long int a, unsigned long long int b)
{
if (power(a,b) < 1000000007)
{
if (b == 1)
return a;
else
return a * power(a, b-1);
}
else if (power(a,b) == 1000000007)
return 0;
else
return a * power(a, b-1) % 1000000007;
}
int main()
{
unsigned long long int a, b;
scanf("%llu %llu", &a, &b);
printf("%llu", power(a,b));
return 0;
}
Рассмотрите возможность использования эффективного алгоритма возведения в степень с модулем, применяемым к каждому шагу операции. Ваше рекурсивное решение - это наихудший из возможных способов.
Ответы 1
Вот эффективное решение возведения в степень:
#include <stdio.h>
unsigned long long power(unsigned long long base, unsigned long long exp, unsigned modulo)
{
unsigned long long result = 1;
base %= modulo;
for (;;)
{
if (exp & 1)
result = (result * base) % modulo;
exp >>= 1;
if (!exp)
break;
base = (base * base) % modulo;
}
return result;
}
int main(void) {
unsigned long long int a, b;
if (scanf("%llu %llu", &a, &b) != 2)
return 1;
printf("%llu\n", power(a, b, 1000000007));
return 0;
}
Некоторые незначительные моменты. 1) Угловая ошибка: power(2,0,1) возвращает 1, когда ожидается 0: result = 1; --> result %= modulo; или тому подобное. 2) Обрабатывать unsigned long long module или когда unsigned 64-битная — это работа. 3) проблема с 1000000007, когда unsigned 16-битное.
Поскольку modulo — это unsigned, функция может также вернуть unsigned вместо unsigned long long и использовать unsigned result.
@chux-ReinstateMonica да, это просто пример. ОП использовал long long, поэтому я остался с этим. В случае модуля 1 я бы поймал это раньше, так как все результаты будут 0.
Что заставляет вас думать, что происходит переполнение? Пожалуйста, покажите нам пример вывода, который вы видите, и то, что вы ожидаете.