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

Thứ sáu - 05/05/2023 17:14 3.649 0

Đức đang làm các bài tập về số học. Đức rất thích số hoàn hảo, đó là các số nguyên dương n mà tổng các ước dương (khác n) của n có giá trị bằng n. Ví dụ, n = 6 là số hoàn hảo, vì 6 có các ước khác 6 là 1,2,3; tổng 1 + 2 + 3 = 6. Tuy nhiên, bài tập mà thầy giáo ra cho Đức là số không hoàn hảo. Một số nguyên dương n được gọi là số không hoàn hảo nếu tổng các ước dương (khác n) của n có giá trị lớn hơn n. Ví dụ, n = 12 là số không hoàn hảo vì 12 có các ước khác 12 là 1, 2, 3, 4, 6; tổng 1+2 + 3 + 4 + 6 = 16 lớn hơn n = 12

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ụ

KhongHoanHao.Inp

KhongHoanHao.Out

Giải thích

2 20

Có 3 số không hoàn hảo thuộc đoạn [2,20] là: 12,18,20.

Số 12, có các ước khác 12: 1,2,3,4,6; tổng 1+2+3+4+6 = 16 lớn hơn 12.
Số 18, có các ước khác 18: 1,2,3,6,9; tổng 1+2+3+6+9 = 21 lớn hơn 18.
Số 20, có các ước khác 20: 1,2,4,5,10; tổng 1+2+4+5+10 = 22 lớn hơn 20.

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.