NKABD spoj – Số phong phú

Nguồn đề bài: http://vn.spoj.com/problems/NKABD/

1. Đề bài NKABD spoj

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].

Dữ liệu

Gồm 2 số L, R (1 <= L <= R <= 10⁵)

Kết quả

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

Chú ý

Có 50% số test có 1 <= L <= R <= 10³

Ví dụ

Dữ liệu
1 50

Kết quả
9

Giải thích:
Từ 1 đến 50 có 9 số phong phú là:
12, 18, 20, 24, 30, 36, 40, 42, 48

=========================
Bài này kêu gì làm đó thôi 😀 chỉ có phần kiểm tra ước. các bạn chỉ cần tìm từ 2->sqrt(n) thôi. vì cái này liên quan đến toán và đã được chứng minh nên mình ko nhắc lại.

2. code tham khảo NKABD spoj (pascal)

program bt;
const   fi='';
        fo='';
var
        f:text;
        a,b:longint;


function check(n:longint):boolean;
var     i:longint;
        S:longint;
begin
        s:=1;
        for i:=2 to trunc(sqrt(n)) do
                if n mod i = 0 then
                	begin
                        	inc(s,i);
                        	if i<>n div i then
                        		inc(s,n div i);
                        	if s>n then exit(true);
                        end;
        exit(s>n);
end;

procedure xuli;
var     i:longint;
        dem:longint;
begin
        dem:=0;
        for i:=a to b do
                if check(i) then
                        inc(dem);
        writeln(f,dem);
end;

begin
        assign(f,fi); reset(f);
        readln(f,a,b);
        close(f);
        assign(f,fo); rewrite(f);
        xuli;
        close(f);
end.

BCPP spoj PTIT