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

Note

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

Bình luận

ý 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;
}

0

duclong0090 1:01 a.m. 17 Tháng 8, 2024

nghe thuyết phục đấy

3 bình luận nữa