Tìm lũy thừa của lũy thừa modulo số nguyên tố trong C++

Trong bài toán này, cho bốn giá trị A, B, C, M (số nguyên tố). Nhiệm vụ là tìm lũy thừa của lũy thừa modulo số nguyên tố.

Tính giá trị (A ^ (B ^ C)) (mod M).

Ví dụ minh họa:

Đầu vào

A = 3, B = 6, C = 2, M = 11

Đầu ra

3

Giải thích

(A ^ (B ^ C)) = (3 ^ (6 ^ 2)) = (3 ^ 36) mod 11 = 3

Phương pháp giải

Cách trực tiếp: tính B^C, rồi A^(B^C), lấy mod. Nhưng B^C rất lớn, gây tràn số.

Cách hiệu quả: Dùng định lý Fermat nhỏ: a^(M-1) ≡ 1 (mod M) với M nguyên tố.

Biến B^C = x*(M-1) + y. Khi đó A^(x*(M-1)) ≡ 1. Cần tính A^y mod M.

y = B^C % (M-1). Kết quả = A^(B^C % (M-1)) mod M.

Chương trình minh họa:

Ví dụ

#include <iostream> 
using namespace std; 

int calcPowerMod(int x, int y, int p) { 
    int powMod = 1; 
    x = x % p; 
    while (y > 0) { 
        if (y & 1) powMod = (powMod * x) % p; 
        y /= 2; 
        x = (x * x) % p; 
    } 
    return powMod; 
} 

int findPowerOfPowerMod(int A, int B, int C, int M) { 
    return calcPowerMod(A, calcPowerMod(B, C, M-1), M); 
} 

int main() { 
    int A = 3, B = 6, C = 2, M = 11; 
    cout<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M); 
    return 0; 
}

Kết quả

The power of power under modulo is 3