Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

Viết mã C++ thực hiện mô tả sau: ví dụ: 2 số nhập vào là 18 và 29 thì sẽ in ra tất cả…

  1. User

    Viết mã C++ thực hiện mô tả sau: ví dụ: 2 số nhập vào là 18 và 29 thì sẽ in ra tất cả phép tính: 29 = 1 * 18 + 11 18 = 1 * 11 + 7 11 = 1 * 7 + 4 7 = 1 * 4 + 3 4 = 1 * 3 + 1 => 1 = 1 * 4 - 1 * 3 = 1 * 4 - 1(1 * 7 - 1 * 4) = -1 * 7 + 2 * 4 = -1 * 7 + 2(1 * 11 - 1 * 7) = 2 * 11 - 3 * 7 = 2 * 11 - 3(1 * 18 - 1 * 11) = -3 * 18 + 5 * 11 = -3 * 18 + 5(1 * 29 - 1 *18) = 5 * 29 - 8 * 18 => 18^-1(mod29) = -8(mod29) = 21(mod29)

  2. Assistant
    #include <iostream>
    using namespace std;
    
    int gcdExtended(int a, int b, int &x, int &y) {
        if (a == 0) { // Base case
            x = 0;
            y = 1;
            return b;
        }
    
        int x1, y1; // To store results of recursive call
        int gcd = gcdExtended(b % a, a, x1, y1);
    
        // Update x and y using results of recursive call
        x = y1 - (b / a) * x1;
        y = x1;
    
        return gcd;
    }
    
    int main() {
        int a, m;
        cout << "Nhap 2 so nguyen a va m: ";
        cin >> a >> m;
    
        cout << "Cac phep tinh la: " << endl;
        int x0, y0;
        int temp = gcdExtended(a, m, x0, y0);
        while (temp != 1) {
            int c = m / temp;
            cout << m << " = " << c << " * " << a << " + " << m % a << endl;
            m = temp;
            temp = gcdExtended(a, m, x0, y0);
            a = m % a;
        }
        cout << m << " = " << m / temp << " * " << a << " + " << m % a << endl;
    
        int x, y;
        gcdExtended(a, m, x, y);
        cout << "18^-1(mod29) = ";
        if (x < 0) x += m;
        cout << x;
    
        return 0;
    }