Возведение в степень по модулю. Большие числа в си

Здравствуйте! Мне необходимо вычислить: 2147483647^2147483647%2147483648; 2147483647=2^(31)-1; Пожалуйста, подскажите, как реализовать подобное на с?

Ответ

Все очень просто. Понятно, что если умножать числа и потом взять по модулю, то для этого нужна будет длинная арифметика. А число выйдет приличное (более 66,571 миллиардов знаков). Поэтому применим трюк - будет после каждого умножения брать по модулю. То есть, код где то такой (схематически) a = 2147483647; m = 2147483648; for (i = 0; i < 2147483647; i++) { r *=a; r %= m; } Но здесь своя незадача. Работать это дело будет не быстро. Здесь в бой вступает быстрое возведение в степень. Оно работает очень быстро. Но есть ещё один подводный камень. Дело в том, что число то большое и вполне будет переполнение. Здесь можно поступить двояко. либо взять 64битное и все сделать, либо, учитывая, что все равно нужно брать по модулю 2 в 32, использовать следствия переполнения (оно будет работать нам на руку). Вариант с 64битными переменными #include
#define int64 long long int
int64 st(int64 a, int64 b, int64 m) { int64 r = 1; while (b) { if (b & 1) { r *= a; r %= m; } a *= a; a %= m; b >>=1; } return r; }
int main() { int64 a = 2147483647; int64 m = 2147483648; int64 r = st(a,a,m); printf("%lld
", r); return 0; } Вариант с 32битными #include
unsigned int st(unsigned int a, unsigned int b) { unsigned int r = 1; while (b) { if (b & 1) { r *= a; } a *= a; b >>=1; } return r; }
int main() { unsigned int a = 2147483647; unsigned int r = st(a,a); printf("%d
", r); return 0; } p.s все компилировал в gcc строкой gcc test.c -Wall -pedantic -std=c99 на 64 битной системе. Оба варианта выдали 2147483647. На первый взгляд странно. Но потом, взяв обычный листик бумаги, я убедился, что 2147483647 * 2147483647 % 2147483648 равно 1. Отсюда напрашивается вывод, что для (2147483647 ^ a) % 2147483648 равно 1 для всех четных a. и 2147483647 для всех нечетных.