Chương trình C++ triển khai Định lý Euler

Đây là chương trình C++ minh họa việc triển khai Định lý Euler. Số và modulo phải nguyên tố cùng nhau (coprime) để nghịch đảo modulo tồn tại.

Thuật toán

Bắt đầu
    Nhập số để tìm nghịch đảo modulo
    Nhập giá trị modulo
    Thực hiện hàm mảng nghịch đảo: modInverse(x + 1, 0); modInverse[1] = 1;
    Với i = 2 đến x
        modInverse[i] = (-(y / i) * modInverse[y mod i]) mod y + y
    Trả về modInverse
Kết thúc

Mã ví dụ

#include <iostream> 
#include <vector> 
using namespace std; 

vector<int> inverseArray(int x, int y) { 
    vector<int> modInverse(x + 1, 0); 
    modInverse[1] = 1; 
    for (int i = 2; i <= x; i++) { 
        modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y; 
    } 
    return modInverse; 
} 

int main() { 
    vector<int>::iterator it; 
    int a, m; 
    cout << "Nhập số để tìm nghịch đảo modulo: "; 
    cin >> a; 
    cout << "Nhập giá trị modulo: "; 
    cin >> m; 
    cout << inverseArray(a, m)[a] << endl; 
}

Kết quả

Nhập số để tìm nghịch đảo modulo: 26 
Nhập giá trị modulo: 7 
7