Bagaimana untuk Mengira dengan Cekap (a^b)%MOD dengan Eksponen Besar?

Mengira (a^b)%MOD dengan Eksponen Besar

Dalam cabaran pengekodan ini, tugasnya adalah untuk mengira nilai pow( a, b)%MOD, di mana eksponen b boleh menjadi sangat besar. Walaupun kaedah kerumitan masa log(b) konvensional sesuai untuk nilai yang lebih kecil, ia menjadi tidak praktikal apabila b melebihi kapasiti jenis data yang panjang dalam C .

Walau bagaimanapun, pendekatan yang lebih cekap melibatkan memanfaatkan fungsi totien Euler, φ(MOD). Teorem Euler menyatakan bahawa a^φ(MOD)≡1(mod MOD). Ini bermakna kuasa a boleh dikurangkan dengan ketara kepada a^(b % φ(MOD)).

Mengira φ(MOD) itu sendiri adalah tugas yang tidak remeh, tetapi boleh dicapai menggunakan kaedah pemfaktoran integer . Setelah dikira, eksponen b boleh digantikan dengan b % φ(MOD) untuk mengurangkan masa pengiraan secara mendadak.

Pemurnian Lanjut

Pada tahun 2008, Schramm menunjukkan bahawa φ (b) boleh didapati daripada penjelmaan Fourier diskret bagi gcd(b, i), untuk i antara 1 hingga b. Ini menghapuskan keperluan untuk pemfaktoran eksplisit.

Selain itu, fungsi Carmichael, λ(MOD), boleh digunakan untuk mendapatkan jawapan yang betul, terutamanya apabila a dan MOD berkongsi faktor sepunya.

Pelaksanaan Kod

Coretan kod berikut berfungsi sebagai contoh dalam C :

<code class="cpp">#include <iostream>
#include <vector>

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 << pmod(a, b % phi(mod), mod) << endl;
    return 0;
}</code>

Atas ialah kandungan terperinci Bagaimana untuk Mengira dengan Cekap (a^b)%MOD dengan Eksponen Besar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!