Tin học Số gần hoàn hảo C++

[chicken1568]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

MỌi người giúp em code bài 1 với ạ, hoặc cho em xin thuật toán vì em không thể hiểu sai ở đâu :')

 

[quoclanxxx]

Spoiler: Hướng tiếp cận

Đề hỏi gì làm đó: Tính tổng các ước [TEX]K[/TEX] của [TEX]A[/TEX], kiểm tra điều kiện [TEX]2\cdot A \leqslant K[/TEX] có thỏa mãn không, nếu có thì ta đưa ra làm kết quả.

Mã giả:

function count_almost_perfect_numbers
{
    for number in array do
        if number is almost_perfect then
            push number to result_array
    print(size of result_array)
    for number in result_array
        print(number)
}

(P/s: mình sẽ chỉ làm mẫu hàm kiểm tra một số có gần hoàn hảo thôi, phần code đầy đủ bạn tự code lại nhé :3)

Spoiler: Method 1

Để tính tổng các ước của [TEX]A[/TEX], ta có thể làm một vòng duyệt đơn giản từ [TEX]1[/TEX] đến [TEX]A[/TEX], kiểm tra xem nếu số [TEX]A[/TEX] chia hết thì cộng nó vào tổng [TEX]K[/TEX], rồi xét.

Code (C++):

bool check_almost_perfect(int a)
{
    int k = 0;
    for (int i = 1; i <= a; i++)
        if (a%i == 0) k += i;
    return (2*a <= k);
}

Độ phức tạp: [TEX]O(N\cdot A)[/TEX], với [TEX]N[/TEX] là số lượng số cần nhập, và [TEX]A[/TEX] là số lớn nhất trong mảng đó.
Với giới hạn đề bài, số lượng phép tính tối đa cần thực hiện với method này là [TEX]10^{10}[/TEX], thành ra method này chưa tối ưu.

Spoiler: Method 2

Để ý là với [TEX]i[/TEX] là một ước của [TEX]A[/TEX] thì [TEX]A/i[/TEX] cũng là một ước của [TEX]A[/TEX]. Do đó, ta có thể tối ưu code của method 1 bằng cách:

• Chỉ duyệt từ [TEX]1[/TEX] đến [TEX]\sqrt{A}[/TEX].
• Với mỗi ước [TEX]i[/TEX] ta kiểm tra thêm nếu [TEX]i \neq A/i[/TEX] thì [TEX]A/i[/TEX] cũng là một ước của [TEX]A[/TEX].

Code (C++):

bool check_almost_perfect(int a)
{
    int k = 0;
    for (int i = 1; i <= sqrt(a); i++)
        if (a%i == 0)
        {
            k += i;
            if (i != a/i) k += a/i;
        }
    return (2*a <= k);
}

Độ phức tạp: [TEX]O(N\sqrt{A})[/TEX], và với giới hạn đề bài ta được số phép tính tối đa cần thực hiện là [TEX]10^7[/TEX], vừa đủ để ta AC.

Chúc bạn học tốt nha. ^^