Số phong phú

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Thời gian:
Python 3 10.0s
Bộ nhớ:
Python 3 512M
Tác giả:
Small
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số \(12\) có tổng các ước số (không kể \(12\)) là \(1 + 2 + 3 + 4 + 6 = 16 > 12\). Do đó \(12\) là một số phong phú.

Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [\(L,R\)].

Input

  • Gồm 2 số \(L, R\) (\(1 \leq L \leq R \leq 10^6\))

Output

  • Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [\(L, R\)].

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(1 \leq L \leq R \leq 10^3\)
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm

Example

Test 1

Input 
1
50
Output 
9
Note

Từ \(1\) đến \(50\) có \(9\) số phong phú là: \(12, 18, 20, 24, 30, 36, 40, 42, 48\)

Bình luận


  • -1
    vietnammuonnam_mvn    5:21 p.m. 31 Tháng 8, 2024

    import math

    def sum_of_divisors(n):
    # Hàm tính tổng các ước số của n (không kể chính nó)
    total = 1
    sqrt_n = int(math.sqrt(n))
    for i in range(2, sqrt_n + 1):
    if n % i == 0:
    total += i
    if i != n // i:
    total += n // i
    return total

    def count_abundant_numbers(L, R):
    count = 0
    for i in range(L, R + 1):
    if sum_of_divisors(i) > i:
    count += 1
    return count

    Đọc dữ liệu đầu vào

    L, R = map(int, input().split())

    Đếm số phong phú trong đoạn [L, R]

    result = count_abundant_numbers(L, R)

    Xuất kết quả

    print(result)
    Code này sai ở đâu vậy


    • 2
      lehongduc    7:05 p.m. 18 Tháng 6, 2024 ← chỉnh sửa 14
      ý tưởng

      bài này mình sử dụng sàng số đếm ước
      mình tạo một mảng khởi tạo bằng 0
      chạy từ 2 đến <=r/2
      mỗi vòng chạy từ 2 cho đến <r/i (i là vòng lặp trên) tăng phần tử thứ i*j mảng thêm i xong rồi chạy từ r->l nếu i<a[i] thì dem++;

      code c++ 
      #include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll l,r;
    cin>>l>>r;
    vector<ll> a(r+1,0);
    for(ll i=2;i<=r;i++)
    {
        for(ll j=2;j*i<=r;j++)
        {
            a[j*i]+=j;
        }
    }
    ll dem=0;
    for(ll i=l;i<=r;i++)
    {
        if(a[i]>i) dem++;
    }
    cout<<dem;
}
      1 phản hồi

      • -13
        PY1BTranGiaKhang    4:32 p.m. 12 Tháng 11, 2023

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


        • 6
          tula    10:24 p.m. 8 Tháng 6, 2022

          Bài này lập hàm kiểm tra xem tổng các ước của n trừ có lớn hơn n không rồi cho chạy từ l đến r, kiểm tra i nếu có thì d++ lên thôi. Mà vẫn Runtime 1 test

          2 phản hồi