Найти по модулю деления очень больших чисел

Question

Я должен найти по модулю деления этого числа:

239^(10^9) и 10^9 + 13

239^(10^9) и 10^9 + 15

... и т.д. до 1001;

Использование только родных библиотек в C++. Как это сделать? Как вы можете видеть, первое число составляет около 3 миллиардов символов.

Я пробовал найти длину модульных периодов, но они больше, чем 10, и даже unsigned long long int не могут иметь дело с такими большими числами (239^10). Также я думаю, что алгоритмы «больших чисел» (сохранение числа в виде массива) тоже не будут работать для меня (500 * 10^9) - это слишком много операций.

Кстати, это должно работать меньше, чем через 5 часов.

Answer 1

Мы знаем, что:

(A*B) % MOD = ((A % MOD) * (B % MOD)) % MOD 

Так

(A^n) % MOD = (((A^(n/2)) % MOD) * ((A^(n/2)) % MOD)) % MOD; 

И мы можем сделать это рекурсивно.

Итак, вот наша функция:

int cal(int pow, int val, int MOD){ 
    if(pow == 0) 
     return 1; 
    int v = cal(pow/2, val, MOD); 
    if(pow % 2 == 0) 
     return (v*v) % MOD; 
    else 
     return (((v*val) % MOD) * v) % MOD; 
}