Tăng tốc bài toán tính tổng các của n (trừ n)

kkkbik · November 27, 2019, 3:52pm

Đề: Nhập n vào từ bàn phím
KQ: in ra tổng các ước số nhỏ hơn n(Trừ n)
Em làm như vậy mà bị lỗi thời gian ko đúng so với quy định :(( Cao nhân nào có ý kiến gì thì giúp em với ạ!

#include <iostream>
using namespace std;
int main()
{
    int n, s = 0;
    cin >> n;
    for (int i = 1; i < n; i++)
        if (n%i == 0)
            s = s + i;
    cout << s;
    return 0;
}

Dao_An · March 16, 2017, 3:28pm

Thử chạy đến n/2 xem …

kkkbik · March 16, 2017, 3:38pm

Vẫn thế anh ơi… Nó cũng đc 50/100 thôi à :((

Dao_An · March 16, 2017, 3:50pm

Xác định xem số đó là chẵn hay lẻ rồi chạy vòng lặp với step = 2 xem.
p/s: ko biết với C++ thì có nhanh hơn ti nào ko :))

kkkbik · March 16, 2017, 3:52pm

Vẫn như cũ…

drgnz · March 16, 2017, 4:01pm

Bạn có thể chạy tới căn n. Sau đó tìm 1 lần 2 ước = cách lấy n / i ra ước t2.
Cẩn thận trường hợp i^2 = n

nhatlonggunz · March 16, 2017, 4:04pm

Bạn chỉ cần chạy tới sqrt(n).
Nếu i là ước của n thì n/i cũng là ước của n.
Độ phức tạp là O(sqrt(n)).

À, như bác @drgnz nói =)))

noz1995 · March 16, 2017, 4:04pm

Cách này chắc là lâu hơn :))
https://maytinhbotui.vn/Forums/Topic/cong-thuc-tinh-tong-cac-uoc-cua-mot-so

kkkbik · March 16, 2017, 4:05pm

> #include <iostream>
> #include <math.h>
> using namespace std;
> int main()
> {
> 	int n, s = 0;
> 	cin >> n;
> 	for (int i = 1; i <= sqrt(n); i++)
> 		if (n%i == 0)
> 			s += (i + n / i);
> 	cout << s;
> 	return 0;
> }

Đây ạ. Chạy tới căn n. Nhưng nó vẫn tính luôn n trong đó :((

KhoaTran · March 16, 2017, 4:08pm

Các ước số của n không vượt quá căn bậc 2 của n nên bạn xét đến căn bậc 2 của n thôi nha.

rogp10 · March 17, 2017, 5:30am

Nếu n chính phương thì phải trừ lại đó thôi thì ghi i < sqrt(n) rồi xét riêng.

Để không dính n thì chạy từ 2 lên rồi khởi tạo s = 1.

Câu này ko chuẩn thực ra nó ntn:

Với mọi hợp số luôn có d | n sao cho 1 < d < n. Nếu 1 < d <= sqrt(n) thì không nói gì. Ngược lại, n > d > sqrt(n) <=> 1/n < 1/d < 1/sqrt(n) <=> 1 < n/d < n/sqrt(n) = sqrt(n). Mà d | n vậy n/d là số nguyên (tính chất phép chia) và (n/d) | n.

Hay nói cách khác, d với n/d là một cặp và một trong hai không vượt quá sqrt(n). Vậy mới ổn.

rogp10 · March 17, 2017, 1:54am

Cách này dùng để duyệt thôi. Nếu muốn tối ưu thì phân tích ra TSNT rồi tính

TamNinja · March 17, 2017, 2:02am

kkkbik:

#include <iostream>
using namespace std;
int main()
{
    int n, s = 0;
    cin >> n;
    for (int i = 1; i < n; i++)
        if (n%i == 0)
            s = s + i;
    cout << s;
    return 0;
}

#include <iostream>
using namespace std;
int main() {
    int n, s = 0;
    int pre = 1;
    cin >> n;
    for (int i = 2; i < n / 2; i++) {
        while (n % i == 0) {
            n = n / i;
            pre = pre * i;
            sum = sum + pre;
        }
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    cout << s;
    return 0;
}

Bài toán có hiệu quả khi n lớn. Vậy nên nếu muốn chơi bời hơn thì có thể như sau:

#include <iostream>
using namespace std;
int main() {
    int n = 0;
    int sum = 0;

    cin >> n;
    if (n > 2*2*2*2*2) {
        sum = blad(n);
    } else {
        sum = bladblad(n);
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    cout << s;
    return 0;
}

int blad (int n) {
    int sum = 0;
    int pre = 1;
    cin >> n;
    for (int i = 2; i < n / 2; i++) {
        while (n % i == 0) {
            n = n / i;
            pre = pre * i;
            sum = sum + pre;
        }
    }

    if (n == i && sum > pre) {
        sum = sum - pre;
    }

    return sum
}

int bladblad (int n) {
    int sum = 0;
    for (int i = 2; i < n / 2; i++) {
        if (n % i == 0) {
            sum = sum + i;
        }
    }

    return sum;
}

Câu hỏi là tổng đó có cấp nhận số 1 không? Đang mặc định là anh không lấy số 1 còn em thì có.
Anyway là bài này đúng là phải phân tích ra thừa số nguyên tố mà quên mất thuật toán đó rồi nên em tự tìm lại thuật toán đó nhé. Cơ mà có lẽ dùng cách này sẽ nhanh hơn thì phải.

rogp10 · March 17, 2017, 2:08am

Vẫn sqrt(n) được. Chỉ cần xét sau cùng n có bằng 1 không.

Nếu n bằng 1 thì thừa số cuối cùng có số mũ > 1, vì ta biết rõ chia đến sqrt() là đủ. (và ngược lại)
Nếu n khác 1 thì rõ ràng ta vừa chạy xong test cho n, vậy n nguyên tố.

kkkbik · March 17, 2017, 4:04pm

Tks mod nhiệt liệt và cật lực từ bên congdongcviet tới tận đây.!
Mình đã làm ra rồi ạ! Cảm ơn tất cả mọi người

kkkbik · March 17, 2017, 4:05pm

Nếu tính tổng ước n(trừ n) Thì vẫn lấy số 1 anh ơi. VÌ mọi số chia cho nó đều hết mà

rogp10 · December 12, 2018, 4:52pm

Chính xác. Nhưng chú ý chút: nên viết for(i=2; i<x; ++i) rồi cập nhật lại x để tránh phép tính số thực.

TamNinja · March 20, 2017, 5:22am

Chưa hiểu ý đồ đoạn này lắm…

rogp10 · November 25, 2019, 6:51am

Một dạng quy nạp đấy c/m tổng ước của n bằng tích tổng ước các thừa số nguyên tố của n, hay $S({p_1}^{j_1} * {p_2}^{j_2} * ...) = S({p_1}^{j_1}) * S({p_2}^{j_2}) * ...$ với p1, p2… nguyên tố và đôi một khác nhau.

Đầu tiên đương nhiên S(p1^j1) = S(p1^j1) rồi. Xét $n' = n * {p_i}^{j_i}$ với gcd(p_i, n) = 1 ta có $d\ |\ n \Leftrightarrow {p_i}^k*d\ |\ {p_i}^k*n$ (với $k = 0...j$ ) $\Rightarrow {p_i}^k*d\ |\ {p_i}^{j_i}*n$ . Tức là các ước của n’ có dạng $p_i^k*d$ . Cộng lại:
$\sum_{k=0}^{j_i} \sum_{d|n}\left(p_i^k*d\right)\\ = \sum_{k=0}^{j_i} \left(p_i^k * \sum_{d|n}d\right)\\ = \sum_{k=0}^{j_i} \left(p_i^k * S(n)\right)\\ = S(n) * \sum_{k=0}^{j_i} \left(p_i^k\right)\\ = S(n) * S\left({p_i}^{j_i}\right)\\$

Suy ra đpcm.

S(2) = 1+2 = 3, nếu nhân bừa thì S(2*2) =? 3*3 = 9 (SAI) vì ước của 4 là {1, 2, 4} chứ không phải {1, 2, 2*1, 2*2}.

C/m trên sử dụng tính phân tích duy nhất của một số nguyên, còn tổng quát là đây:

sigma

nhatlonggunz · March 25, 2017, 3:04am

Phân tích ra TSNT lâu hơn việc for các ước mà bạn ?