Calcul (a^b)%MOD avec de grands exposants

Dans ce défi de codage, la tâche consiste à calculer la valeur de pow( a, b)%MOD, où l'exposant b peut être extrêmement grand. Bien que la méthode conventionnelle de complexité temporelle log(b) soit adaptée aux valeurs plus petites, elle devient peu pratique lorsque b dépasse la capacité des types de données long long en C .

Cependant, une approche plus efficace implique d'exploiter la fonction totient d'Euler, (MOD). Le théorème d'Euler stipule que a^φ(MOD)≡1(mod MOD). Cela signifie que la puissance de a peut être considérablement réduite à a^(b % φ(MOD)).

Le calcul de φ(MOD) est en soi une tâche non triviale, mais peut être réalisé à l'aide de méthodes de factorisation entières. . Une fois calculé, l'exposant b peut être remplacé par b % φ(MOD) pour réduire considérablement le temps de calcul.

Autres raffinements

En 2008, Schramm a démontré que φ (b) peut être obtenu à partir de la transformée de Fourier discrète de pgcd(b, i), pour i allant de 1 à b. Cela élimine le besoin d'une factorisation explicite.

De plus, la fonction de Carmichael, λ(MOD), peut être utilisée pour obtenir la bonne réponse, en particulier lorsque a et MOD partagent des facteurs communs.

Implémentation du code

L'extrait de code suivant sert d'exemple en 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