BCPP - Số phong phú

Link Sub: http://www.spoj.com/PTIT/problems/BCPP/
Người Gửi: Sai

• Problem:

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 <= L <= R <= 106)
Có 50% số test có 1 <= L <= R <= 103

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

Example:

Input

1 50

Output:

9

• Solution:

Từ 1 đến 50 có 9 số phong phú là: 12, 18, 20, 24, 30, 36, 40, 42, 48
Với cách duyệt trâu độ phức tạp lên tới O(10^9). -> Vậy nên cần một cách cải tiến của cách tìm ước số. - Cách làm: + Tư tưởng là sẽ làm theo cách sàng nguyên tố Eratosthenes. VD: khởi tạo từ 1->10^6; Với 1 ta có [10^6/1] số >= 1 và <= 10^6: Cộng 1 vào các số là bội của 1 (arr[1]=1, arr[2]=1, arr[3]=1, ... arr[6]=1,...); Với 2 ta có [10^6/2] số >= 2 và <= 10^6: Cộng 2 vào các số là bội của 2 (arr[1]=1, arr[2]=3, arr[3]=1, ... arr[6]=3,...); ... Cứ như vậy cho hết 10^6 ta sẽ thu được tổng các ước của của các số i:1->10^6 trong đó SUMDIV_i = arr[i]. Với độ phức tạp chỉ còn khoảng O (10^7). Vẫn tạm nhanh ^^. + Cuối cùng chỉ cần đếm số phong phú trong đoạn L, R thôi...

• Code:

C++:

JAVA:

Author : DL

Share this

Related Posts