Ước số chung

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 640M

Authors:
Problem type

Số nguyên dương \(𝑝\) gọi ước số chung của \(𝑛\) 𝑣à \(𝑚\) khi \(𝑚\) 𝑣à \(𝑛\) cùng chia hết cho \(𝑝\). Viết chương trình nhập vào một số nguyên dương \(𝑛,𝑚\) (\(𝑛,𝑚 ≤ 10^7\)). Hãy in ra tất cả các ước số chung của \(𝑛\) 𝑣à \(𝑚\).

Input:

  • Hai số nguyên dương \(𝑛,𝑚\),

Output:

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

Ví dụ

Input

54 72

Output

1 2 3 6 9 18

View comments (8)

Comments


  • 2
    Toilaaibanbietko7A4  commented on 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.


  • -12
    minhkhoidepzai  commented on 3:44 p.m. 29 nov, 2020

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


  • 2
    SPyofgame  commented on 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
     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    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;
    }