Ước số chung

Xem PDF
Tác giả:
admin , daicadihoc
Dạng bài
Điểm: 100 Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Số nguyên dương \(p\) gọi là ước số chung của \(n\) 𝑣à \(m\) khi \(m\) 𝑣à \(n\) cùng chia hết cho \(p\).

Viết chương trình nhập vào một số nguyên dương \(n,m\) (\(n,m \leq 10^{7}\)).

Hãy in ra tất cả các ước số chung của \(n\) 𝑣à \(m\).

Input

  • Nhập \(2\) số nguyên dương \(n,m\).

Output

  • In ra các ước số chung của chúng.

Example

Test 1

Input 
54 72
Output 
1 2 3 6 9 18

Bình luận


  • 6
    SPyofgame    9:07 p.m. 7 Tháng 6, 2020

    Spoiler Alert

    Hint 1

    Gọi D(x) là tập hợp các ước của x

    Cần tìm D(x) = D(m) ∩ D(n)

    Hint 2

    D(gcd(m, n)) = D(m) ∩ D(n)

    Hint 3

    **D(x) = {y ∈ D(x) | y ≤ k} Λ {z ∈ D(x) | z > k} **

    Reference

    C++
    int main()
{
    /// Nhan gia tri
    int n = readInt();
    int m = readInt();
    int x = gcd(n, m);

    vi l_divisors; /// {y ∈ D(x) | y ≤ k}
    vi h_divisors; /// {z ∈ D(x) | z > k}

    /// Tim cac uoc
    int sqrtx = sqrt(x);
    for (int i = 1; i <= sqrtx; ++i)
        if (x % i == 0)
            l_divisors.pb(i),
            h_divisors.pb(x / i);

    /// Tach phan chung khi (x) la so chinh phuong
    if (l_divisors.back() == h_divisors.back()) h_divisors.pop_back();
    reverse(all(h_divisors));

    /// In ket qua
    for (int x : l_divisors) cout << x << ' ';
    for (int x : h_divisors) cout << x << ' ';
    return 0;
}
    • 3 bình luận nữa