[Lập trình newbie] Mỗi ngày một bài toán (số 15)

[09520281]

Hi all, đã quá lâu mình mới lập lại toppic này, thời gian qua nhiều việc luxubu quá nên chưa ra bài số 15 được :sweat:, hum nay tình hình là có mấy em tân sinh viên mới vào nên làm phát cho nó rôm rả phong trào nhỉ. Không biết BQT có phần thưởng gì mang tính khích lệ tinh thần cho các bạn đã tham gia giải 14 số trước không :smile:. Sau đây bài toán số 15: (đơn giản cho mấy bạn tân sinh viên tập làm :sunglasses.
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].
Time limit: 1s
Memory: 5MB
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
Chúc mọi người ngày mới vui vẻ :salute:

[quoctinvn]

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int l,r,i,j,res,sum;
    scanf("%d\n",&l);
    scanf("%d",&r);
    res = 0;
    for (i=l;i<=r;i++)
    {
        sum = 1; j = 2;
        while (j*j <= i)
        {
            if ((i%j)==0)
            {
                sum += j;
                if (j*j < i) sum += (i/j);
            };
            j++;
        };
        if (sum > i) res++;
    };
    printf("%d",res);
    return 0;
}

Với mỗi số i trong đoạn [L,R]. ta xét xem những số j nào từ 1 --> căn bậc 2 của i mà i chia hết cho j. Tổng ước sẽ là tổng của các số j và i/j :happy:

[10520355]

quoctinvn học C nhanh ghê ta. hi. good good.

[kengo14]

Chào bạn.Mình ko hiểu tại sao chỉ xét đến căn bậc 2 ???

[quoctinvn]

Căn bậc 2 thì bình phương lên >= số đó. Nên luôn tồn tại 1 số k lớn hơn hoặc bằng số x thuộc [căn bậc 2 số đó, số đó] sao cho số đó chia cho k có kq nằm từ 1 -> căn bậc 2 :byebye:

[10520355]

ta thấy j x k = i thì j và k đều là ước của i. Ta để ý khi k=j thì j² = i ===> j= căn của i ; Vậy j chỉ cần chạy đến căn i thôi, ước còn lại sẽ là k=i/j

[kengo14]

Ah. Cám ơn các bạn, mình thì hiểu thế này. Một số phong phú là 1 số có tổng các ước của nó > nó. Vậy nói chung để làm bài này ta chỉ cần tìm tất cả các ước của số đã cho ( gọi là n) và cộng lại thôi đúng ko ạ? Vậy ta phải xét trong khỏang từ 1 -> n rồi lấy tất cả những số mà n chia hết cho số đó.
Nếu như cách bạn làm thì chỉ tìm trong khỏang 1 -> căn n thôi. Mình thì thắc mắc là có mấy số lớn hơn căn n mà vẫn bị n chia hết đó chứ. Ví dụ như n =81 , căn n = 9 , ta vẫn có 27 là ước của n , không biết mình có lộn gì ko ^^

[08520001]

Đúng là xét từ 1 -> n, rồi lấy tổng các số i mà n chia hết cho i. Nhưng nếu làm cách đó mà n lớn thì sẽ chạy chậm (vd n > 10^12). Do đó cần cải tiến 1 xíu để chạy nhanh hơn.
Với n = 81, thì 27 là ước của 81, và 27 * 3 = 81. Do đó khi xét i từ 1 đến căn n (i: 1 -> căn 81 = 9) thì khi i = 3, ta đã lấy số 3 và số n / i là 27 rồi. Do đó chỉ cần chạy đến căn n là đủ giay cao nam. và tiết kiệm được rất nhiều thời gian.

[10520355]

ví dụ của bạn đây. n=81, căn n = 9.
vậy ta cho i chạy từ 1 đến 9. mình sẽ có được các ước i và n/i
các ước i là: 1 3 9
các ước n/i là : 81 27 9
vì vậy khi duyệt từ 1 -> căn n thì mình sẽ có được tất cả các ước của n mà. (duyệt đến n sẽ làm chậm chương trình với n lớn đấy)

[11520132]

Ah. Cám ơn các bạn, mình thì hiểu thế này. Một số phong phú là 1 số có tổng các ước của nó > nó. Vậy nói chung để làm bài này ta chỉ cần tìm tất cả các ước của số đã cho ( gọi là n) và cộng lại thôi đúng ko ạ? Vậy ta phải xét trong khỏang từ 1 -> n rồi lấy tất cả những số mà n chia hết cho số đó.
Nếu như cách bạn làm thì chỉ tìm trong khỏang 1 -> căn n thôi. Mình thì thắc mắc là có mấy số lớn hơn căn n mà vẫn bị n chia hết đó chứ. Ví dụ như n =81 , căn n = 9 , ta vẫn có 27 là ước của n , không biết mình có lộn gì ko ^^

Thế này ha. Giả sử ta có n= a*a + b ( Với (a+1)*(a+1) > n) >> sqrt(n) ~ a.
Với i<a thì n/i = j > a. Do vậy chỉ cần xét i<a , nếu i thỏa là ước thì cộng thêm n/i=j, vì nếu i*j=a thì cả i và j đều là ước. Và j chính là ước lớn hơn a ~sqrt(n) mà cậu đang nói.
Thật ra thì code của bạn Quốc Tín đã ổn lắm rồi. Nhưng nếu đặt điều kiện dừng ngay khi sum > n thì càng nhanh hơn. Nghĩa là khi sum > n rồi thì không cần tiếp tục vòng lặp xét tới căn n nữa.

[11520447]

Tinh thần UIT là đây
1 câu hỏi 3 người rep tận tình.
Tình thần UIT bất diệt, muôn năm, muôn năm !!!:byebye:

[kengo14]

Ah. Hiểu ùi, hehe , rất cảm ơn mọi người. ^^. Em là newbie Khoa học máy tính K7 nên gà lắm.

[quoctinvn]

cùng khoa, hẹn gặp bạn ở UIT :embarrassed:

Ah. Hiểu ùi, hehe , rất cảm ơn mọi người. ^^. Em là newbie Khoa học máy tính K7 nên gà lắm.

[12520527]

ep 16 đi ạ :haha: