Số không hoàn hảo | Câu 1 - Đề thi HSG tin 12 Nghệ An | năm học 2022 - 2023

Yêu cầu: Cho hai số nguyên dương a và b (2<=a<=b<=10^5). Tính xem có bao nhiêu số không hoàn hảo thuộc đoạn [a,b], tức là tính xem có bao nhiêu số nguyên dương n thỏa mãn: a <= n <=b và n là một số không hoàn hảo.

Dữ liệu cho trong tệp văn bản KhongHoanHao.Inp gồm hai số nguyên dương a và n được ghi trên 1 dòng và cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản KhongHoanHao.Out gồm một số nguyên duy nhất là số các số không hoàn hảo thuộc đoạn [a,b].

Giới hạn:

• Có 90% số test ứng với 90% số điểm thỏa mãn: 2<=a<=b<=1000
• Có 10% số test ứng với 10% số điểm thỏa mãn: 1000<=a<=b<=10^5

Ví dụ

Trước khi em giải, các bạn xem thêm các câu còn lại của đề nhé trong các link sau:

Câu 2. Ổ điện.

Câu 3. Dãy số đẹp

Câu 4. Khởi nghiệp

Giải. 
 

import math

def not_deficient(n):
    sum_divisors = 1
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            div1 = i
            div2 = n / i
            sum_divisors += div1 + div2
            if div1 == div2:
                sum_divisors -= div1
    return sum_divisors > n

with open('KhongHoanHao.Inp', 'r') as f:
    a, b = map(int, f.readline().split())

count = 0
for n in range(a, b + 1):
    if not_deficient(n):
        count += 1

with open('KhongHoanHao.Out', 'w') as f:
    f.write(str(count))

Giải thích:

Trong đó, hàm `not_deficient(n)` được sử dụng để kiểm tra xem một số `n` có phải là số không hoàn hảo hay không. Hàm này tính tổng tất cả các ước của `n` bằng cách duyệt qua các ước từ 2 đến căn bậc hai của `n` và kiểm tra xem số đó có phải là ước của `n` không. Nếu có, hàm sẽ tính ra cặp ước `div1` và `div2`, và thêm tổng của 2 ước này vào biến `sum_divisors`. Nếu `div1` và `div2` bằng nhau, tức là `n` có một ước là căn bậc hai của `n`, hàm sẽ trừ lại `div1` khỏi `sum_divisors`. Cuối cùng, nếu `sum_divisors` lớn hơn `n`, hàm trả về `True` (nghĩa là `n` là số không hoàn hảo), ngược lại trả về `False`

Sau đó, chương trình sử dụng vòng lặp để duyệt qua tất cả các số từ `a` đến `b`, và tăng biến `count` lên 1 nếu số đó không hoàn hảo (tức là hàm `not_deficient` trả về `True`). Cuối cùng, chương trình xuất giá trị của `count` ra tệp KhongHoanHao.Out.

Chú ý:

Khi tìm ước của số n, ta chỉ xét từ 2 đến phần nguyên của căn bậc hai của n. Ở đây chắc sẽ có không ít bạn thắc mắc tại sao lại như vậy (?!) Để hiểu tại sao lại như vậy thì ta xét số n = 64. Các ước của 64 là: Ư(64) = {1; 2; 4; 8; 16; 32; 64 }. Ở đây ta chỉ cần xét các ước nhỏ hơn hoặc bằng căn bậc hai của 64 (Tức là các ước nhỏ hơn hoặc bằng 8). Thì ta dễ dàng tìm được ước của 64 mà lớn hơn 8 bằng cách lấy 64 chia cho các ước nhỏ hơn 8. Ví dụ 2 là ước của 64 thì64:2 = 32 cũng là ước của 64; Tương tự 4 là ước của 64 thì 64:4 = 16 cũng là ước của 64.

 

Để nắm được thông tin cập nhật mới cũng như phản hồi về trang, các bạn tham gia nhóm facebook:

Nhóm facebook: f / BAITAPONHA
Trang facebook: f / HỌC MÃI

Nếu thấy hữu ích, xin đừng tiếc cho tôi xin một ĐĂNG KÝ KÊNH và một LIKE. Xin cảm ơn!

Học mãi