Hướng dẫn cho Số phong phú


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)



\(\color{orange}{\text{Hint 1 <Brute-force>}}\)

  • Với mỗi số trong đoạn \([l, r]\) ta thử tính tổng ước và kiểm tra nếu nó thỏa mãn thì tăng biến đếm

\(\color{orange}{\text{Hint 2 <Implementation>}}\)

  • Với mỗi số \([1..r]\) ta tăng các bội của nó lên giá trị của nó.

Giả sử đang duyệt tới số \(x\)

Vì các bội số bé hơn hoặc bằng \(x\) được tăng giá trị lên

Nên \(x\) đã bao gồm tổng các ước của nó

Nên ta chỉ cần tăng biến đếm các số trong đoạn có tổng ước thỏa đề


\(\color{green}{\text{Preference AC Code }}\): Implementation

\(^{^{\color{purple}{\text{Complexity : }} O(n \log n)\ \color{purple}{\text{time}}\ ||\ O(n)\ \color{purple}{\text{memory}}}}\)

C++
int main()
{
    int l, r;
    cin >> l >> r;

    int res = 0;
    vector<int> divsum(r + 1, 0);
    for (int i = 1; i <= r; ++i)
    {
        for (int j = i; j <= r; j += i)
            divsum[j] += i;

        res += (i >= l) && (divsum[i] > 2 * i);
    }

    cout << res;
    return 0;
}


Bình luận