Ước số chung

View as PDF



Authors:
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


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

    summary

    detail


    • 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.


        • 6
          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