Ước số của n

Tác giả:

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

Viết chương trình nhập vào số nguyên \(n\) (\(n\leq 10^7\)). In ra tất cả các ước số của \(n\). (Ước số của \(n\) là các số nguyên mà \(n\) chia hết)

Ví dụ: \(n=10\) thì in ra các số: \(1\) \(2\) \(5\) \(10\)

Input

Một số nguyên dương \(n\).

Output

In ra các ước số của \(n\).

Example

Test 2

Input

Output

1 2 5 10

Test 2

Input

Output

1 2 3 4 6 9 12 18 36

Bình luận

Spoiler Alert

Hint 1

Gọi D(x) là tập hợp các ước của x

**D(x) = {y ∈ D(x) | y ≤ k} Λ {z ∈ D(x) | z > k} **

Hint 2

Đặt k tới đâu, mình chỉ cần duyệt trong O(k) là xong

Hint 3

Có n = a * b và (a < b), theo bđt Cauchy thì a ≤ √n và b > √n

Duyệt tới k = √n là tối ưu nhất

Reference

C++

int main()
{
    /// Nhan gia tri
    int n = readInt();

    vi lower; /// {y ∈ D(x) | y ≤ k}
    vi upper; /// {z ∈ D(x) | z > k}

    /// Tim cac uoc
    int sqrtn = sqrt(n);
    for (int i = 1; i <= sqrtn; ++i)
        if (n % i == 0)
            lower.push_back(i),
            upper.push_back(n / i);

    /// Tach phan chung khi (n) la so chinh phuong
    if (lower.back() == upper.back()) upper.pop_back();
    reverse(all(upper));

    /// In ket qua
    for (int x : lower) cout << x << ' ';
    for (int x : upper) cout << x << ' ';
    return 0;
}

4 bình luận nữa