Ước số chung

View as PDF
All submissions
Best submissions
Authors:
admin , daicadihoc
Problem types
Points: 100 Time limit: 1.0s Memory limit: 640M Input: stdin Output: stdout

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

Comments


  • -17
    NguyenDucBinh1606    9:21 a.m. 19 jul, 2024

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 2
      kay    10:07 p.m. 11 jun, 2024

      import math
      a, b = map(int, input().split())
      c = []
      for i in range(1, min(a, b) + 1):
      if a % i == 0 and b % i == 0:
      c.append(i)
      print(" ".join(map(str,c)))


      • -9
        duolingoduolingo    8:41 p.m. 18 apr, 2024

        This comment is hidden due to too much negative feedback. Click here to view it.


        • 0
          UserName    10:54 a.m. 22 may, 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 sep, 2021 ← edit 2

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


            • 8
              SPyofgame    9:07 p.m. 7 jun, 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 reply