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

[kkkbik (thdung6198)]

> #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 (Trần Ngọc Khoa)]

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]

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

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]

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 (Tâm Ninja)]

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

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 (thdung6198)]

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 (thdung6198)]

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]

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 (Tâm Ninja)]

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

[rogp10]

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 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 với gcd(p_i, n) = 1 ta có (với ) . Tức là các ước của n’ có dạng . Cộng lại:

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:

Tìm cặp số bạn bè (amicable pairs)

Để mình đọc lại đã rồi xong. Tổng quát với m, n nguyên tố cùng nhau thì d1 | m => d1 | mn d2 | n => d2 | mn d1, d2 | mn <=> BCNN(d1, d2) | mn (định nghĩa) Nếu UCLN(d1, d2) != 1 thì UCLN(m, n) != 1 do tích = UCLN * BCNN nên tìm được song ánh {ước của m} x {ước của n} -> {ước của mn} là (d1, d2) => d1d2.

sigma

[nhatlonggunz]

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

[rogp10]

Sai còn nhanh hơn là khác.

• Nếu là số nguyên tố thì bạn chia tới căn n là xong, như nhau.
• Nếu là hợp số dạng pq thì bạn sẽ chia tới căn q thay vì căn pq (nhanh hơn).
• Nói chung càng nhiều thừa số thì càng nhanh, do số bị chia giảm qua mỗi thừa số tìm được.

Tức là cận trên ban đầu là căn(n), sau mỗi thừa số tìm được ta tính lại cận (nhỏ hơn), vì vậy nhanh hơn.

[nhatlonggunz]

Bạn có thể tính độ phức tạp của cả sàng, phân tích, và tính giùm mình được không ?

[rogp10]

Phần này bạn lập topic mới nhé.

[nhatlonggunz]

Mình vẫn đang nói về tăng tốc bài toán tính tổng ước của topic này mà, sao lại lập topic khac.

[rogp10]

Vậy thì sàng để topic khác vậy.

Với cách chia thử thì ai cũng biết tối đa là O(sqrt(n)) phép mod, nhưng trung bình thì bao giờ nó cũng khó tính cực kì. https://cs.stackexchange.com/questions/50326/what-is-the-average-case-complexity-of-trial-division (kết quả là theta(sqrt(n)/log(n)).

Sách Prime Numbers: A Computational Perspective trang 120 có đưa ra một ước lượng khác nhưng không thuyết phục lắm.

[nhatlonggunz]

Thuật toán của mình mình sẽ chạy O(sqrt(N))
Nhưng mình đang hỏi tổng độ phức tạp thuật toán của bạn mà.

[rogp10]

Thực ra thuật toán của bạn sẽ cần [sqrt(n)] - 1 phép mod trong mọi trường hợp.

Phân tích TSNT theo kiểu chia thử sẽ có độ phức tạp phụ thuộc vào căn bậc hai của thừa số nguyên tố lớn nhất (là n nếu n nguyên tố). Nếu tính trung bình thì sẽ là theta(sqrt(n)/logn) phép mod. http://www.sciencedirect.com/science/article/pii/0022404993900939

[nhatlonggunz]

Mình hiểu rồi, cám ơn bạn <3