Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· OpenAIAi2 WildChat-4.8M (AI2)

viết code c++ nhập vào 2 số l, g, hãy tìm 2 số a, b mà có tổng nhỏ nhất sao cho gcd(a,b)…

  1. User

    viết code c++ nhập vào 2 số l, g, hãy tìm 2 số a, b mà có tổng nhỏ nhất sao cho gcd(a,b) == l và lcm(a,b) == g

  2. Assistant

    Dưới đây là một ví dụ về code C++ cho bài toán của bạn:

    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    // Kiểm tra tích của l và g có phải là bội số của chúng không
    bool isValid(long long l, long long g) {
        return (g % l == 0);
    }
    
    // Tìm ước số chung lớn nhất (GCD) của hai số a và b
    long long gcd(long long a, long long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    
    // Hàm chính để tìm a và b
    void findNumbers(long long l, long long g) {
        if (!isValid(l, g)) {
            cout << "-1" << endl;
            return;
        }
    
        long long prod = l * g;
        
        long long a = 1, b = prod;
        // Tính cặp số (a, b) có tổng nhỏ nhất
        for (long long i = l; i * i <= prod; i += l) {
            if (prod % i == 0) {
                long long j = prod / i;
                // Kiểm tra a và b có thỏa mãn điều kiện là GCD và LCM
                if (gcd(i, j) == l && (i * j) / gcd(i, j) == g) {
                    if(i + j < a + b) {
                        a = i;
                        b = j;
                    }
                }
            }
        }
        
        cout << a << " " << b << endl;
    }
    
    int main() {
        long long l, g;
        cout << "Nhap l, g: ";
        cin >> l >> g;
        findNumbers(l, g);
        return 0;
    }
    

    Trong đoạn code trên:

    • Hàm isValid kiểm tra xem có tổ hợp nào của a và b thoả mãn điều kiện không.
    • Hàm gcd tính ước số chung lớn nhất của hai số.
    • Trong hàm findNumbers, ta chạy vòng lặp từ l đến căn bậc hai của l * g và tại mỗi bước nhảy l, ta kiểm tra xem số đó có phải là ước của l * g không. Nếu có, ta tính số đối tác của nó và kiểm tra xem cặp được tính đó có phải là một cặp hợp lệ của a và b không (tức là GCD của chúng bằng l và LCM của chúng bằng g).

    Lưu ý: Khi chạy chương trình, bạn cần nhập giá trị cho l và g khi được yêu cầu.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.