Ướ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


  • -2
    duolingoduolingo    8:41 p.m. 18 Tháng 4, 2024

    summary

    detail


    • 0
      UserName    10:54 a.m. 22 Tháng 5, 2023

      đề bảo là in ra tất cả ước chung chứ có nói là phải sắp xếp các ước từ nhỏ đến lớn đâu, mất một lần WA :((


      • 0
        Toilaaibanbietko7A4    5:49 p.m. 7 Tháng 9, 2021 ← chỉnh sửa 2

        Bài này bộ test nhỏ quá, đề nghị gia tăng độ khó bộ test nha admin.


        • 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;
}
          1 phản hồi