let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

NKABD - Số phong phú

solution.md

Bài này cần biết cách tính tổng các ước của N trong \(O(\sqrt{N})\).

Cách tính khá đơn giản, nếu \(d\) là ước của \(N\) thì \(N/d\) cũng là ước của \(N\). Vì vậy ta thêm kết quả cho \(d + N/d\).

Để không bị trùng lặp ta chỉ duyệt trong khi \(d \leq N/d \Leftrightarrow d^2 \leq N\).

Cần chú ý trường hợp \(d = N/d\).

Ngoài ra, bài này còn có thể làm nhanh hơn bằng cách với mỗi số \(i\), ta duyệt tất cả các bội số của \(i\) rồi cộng \(i\) vào tổng các ước của bội số đó. Phần code khá giống sàng nguyên tố, xem sieve.cpp bên dưới. Độ phức tạp của cách này: \(O(N\log N)\)

main.cpp
Open in Github • Download 
#include <iostream>
using namespace std;

int divisor_sum(int x) {
    if (x==1) return 0;
    int sum = 1;
    for (int d=2; d*d <= x; d++) {
        if (x % d == 0) {
            sum += d;
            if (x/d != d) sum += x/d;
        }
    }
    return sum;
}

int main() {
    int l, r; cin >> l >> r;
    int count = 0;
    for (int i=l; i<=r; i++) if (divisor_sum(i) > i) count++;
    cout << count;
    return 0;
}
sieve.cpp
Open in Github • Download 
#include <iostream>
using namespace std;
#define N 100000
int sum[N+1];

int main() {
    for (int i=1; i<N; i++) {
        for (int j=2*i; j<=N; j += i) sum[j] += i;
    }
    int l, r;
    cin >> l >> r;
    int count = 0;
    for (int i=l; i<=r; i++) count += sum[i] > i;
    cout << count;
    return 0;
}
Comments