Ước số chung

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
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

  • dinhhoangnguyen1903 • 2:26 p.m. 4 Tháng 1, 2025 •

    import math

    Hàm tính GCD của hai số a và b

    def gcd(a, b):
    while b:
    a, b = b, a % b
    return a

    Nhập dữ liệu

    n, m = map(int, input().split())

    Tính GCD của n và m

    g = gcd(n, m)

    Tìm và in tất cả các ước số của GCD

    result = []
    for i in range(1, int(math.sqrt(g)) + 1):
    if g % i == 0:
    result.append(i)
    if i != g // i: # Tránh in lại ước số lớn bằng ước số nhỏ
    result.append(g // i)

    Sắp xếp kết quả theo thứ tự tăng dần

    result.sort()

    In kết quả

    print(" ".join(map(str, result)))

    0
    Phản hồi
    • tbc1107 • 3:07 p.m. 30 Tháng 12, 2024 •

      include <bits/stdc++.h>

      typedef long long ll;
      using namespace std;
      int main(){
      ll n,m;
      cin>>n>>m;
      ll mx=0;
      if (m>n) {
      mx=m;
      }else{
      if (m<n){
      mx=n;
      }
      }
      for (int i=1;i<=mx;i++){
      if ((m%i==0)&&(n%i==0)){
      cout<<i<<" ";
      }
      }
      return 0;
      }

      code bang c++ cho ai can nha(code hoi nqu, chi mang tinh chat tham khao)

      0
      Phản hồi
      • nghianguyen1805 • 10:45 a.m. 21 Tháng 12, 2024 •

        cde đay nha
        n,m = map(int, input() . split())

        i = 1

        while i <=min(n,m) :
        if n% i ==0 and m%i ==0:
        print(i,end=" ")
        i+=1

        0
        Phản hồi
        • NguyenDucBinh1606 • 9:21 a.m. 19 Tháng 7, 2024 •

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

          -17
          Phản hồi
          • kay • 10:07 p.m. 11 Tháng 6, 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)))

            2
            Phản hồi
            • duolingoduolingo • 8:41 p.m. 18 Tháng 4, 2024 •

              Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

              -10
              Phản hồi
              • 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
                Phản hồi
                • 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.

                  0
                  Phản hồi
                  • 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;
}
                    8
                    Phản hồi