Вычисление (a^b)%MOD с большими показателями

В этой задаче по кодированию задача состоит в том, чтобы вычислить значение pow( a, b)%MOD, где показатель степени b может быть очень большим. Хотя обычный метод временной сложности log(b) подходит для меньших значений, он становится непрактичным, когда b превышает емкость длинных типов данных в C .

Однако более эффективный подход предполагает использование функции Эйлера totient, φ(MOD). Теорема Эйлера утверждает, что a^φ(MOD)≡1(mod MOD). Это означает, что степень a можно значительно уменьшить до a^(b % φ(MOD)).

Вычисление φ(MOD) само по себе является нетривиальной задачей, но ее можно решить с помощью методов факторизации целых чисел. . После расчета показатель степени b можно заменить на b % φ(MOD), чтобы значительно сократить время вычислений.

Дальнейшие уточнения

В 2008 году Шрамм продемонстрировал, что φ (b) может быть получено с помощью дискретного преобразования Фурье НОД(b, i) для i в диапазоне от 1 до b. Это устраняет необходимость явной факторизации.

Кроме того, функция Кармайкла λ(MOD) может использоваться для получения правильного ответа, особенно когда и MOD имеют общие факторы.

Реализация кода

Следующий фрагмент кода служит примером на C:

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout