Lỗi khi tính tổng các ước của một số nguyên dương đã phân tích ra thừa số nguyên tố

#21

đâu cần xài value làm gì nữa, xài thẳng *it1 luôn ~.~. Xóa cái biến value đi. Khởi tạo cái vector kia cũng ko cần khổ nhọc vậy đâu, 1 dòng là đủ rồi:

vector<int> analyzation {2, 2, 2, 3, 3, 5};

main cũng ko cần return 0 đâu

int main()
{ // N = 360 => Sum of divisors = 1170
    vector<int> analyzation {2, 2, 2, 3, 3, 5};
    int sum = 1;
    for (auto it1 = analyzation.begin(); it1 != analyzation.end();)
    {
        auto it2 = upper_bound(it1, analyzation.end(), *it1);
        int base = distance(it1, it2);
        sum *= ((pow(*it1, base + 1) - 1) / (*it1 - 1));
        it1 = it2;
    }
    cout << sum;
}
3 Likes
#22

Ừm, mình đã hiểu rồi.
Cuối cùng, mình có 1 thắc mắc nho nhỏ là mình thử sửa cái dòng này:
sum *= ((pow(*it1, base + 1) - 1) / (*it1 - 1));
thành
sum *= ((pow(*it2, base + 1) - 1) / (*it2 - 1));
thì chương trình cho ra kết quả sai. Mình thấy *it2 sau khi sử dụng upper_bound sẽ là giá trị của phần tử có giá trị *it nhưng ở vị trí sau cùng, tức là giá trị giống *it thì sao lại cho ra KQ sai nhỉ?

#23

base là số mũ của *it1 chứ ko phải số mũ của *it2. Hơn nữa it2 có thể là end(a) nên *it2 ko bảo đảm chạy được. Ví dụ khi it1 trỏ tới số 5 cuối cùng thì it2 sẽ là end(a), gọi *it2 nếu may mắn sẽ gây ra runtime error, nếu xui mình chạy nó ko gây lỗi nhưng tới lúc thầy chạy nó gây lỗi thì ăn 0 điểm

3 Likes
#24

OK bạn. Thế bạn cho phép mình mở rộng bài này ra một xíu nhé.
Đoạn code mình hỏi trên là 1 phần của problem này: https://vn.spoj.com/problems/NKABD/
Đây là đoạn code giải đầy đủ của mình:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iterator>

using namespace std;

int SumOfDivisors(int n)
{
    // Phan tich n ra thanh cac thua so nguyen to
    int minPrime[n + 1];
    for (int i = 2; i < (n + 1); ++i) minPrime[i] = 0;
    double sqrt_n = sqrt(n);
    for (int i = 2; i <= (int)sqrt_n; ++i) {
        if (minPrime[i] == 0) {
            for (int j = i*i; j <= n; j += i) {
                if (minPrime[j] == 0)
                    minPrime[j] = i;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (minPrime[i] == 0)
            minPrime[i] = i;
    }
    vector<int> analyzation; // dung de chua cac thua so nguyen to cua n sau khi phan tich
    while(n != 1) {
        analyzation.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    // Algorithm begins here
    int sum = 1;
    for (auto it1 = analyzation.begin(); it1 != analyzation.end();) {
        auto it2 = upper_bound(it1, analyzation.end(), *it1);
        int base = distance(it1, it2);
        sum *= ((pow(*it1, base + 1) - 1) / (*it1 - 1));
        it1 = it2;
    }
    return sum;
}

int main()
{
    int l, r, c = 0;
    cin >> l >> r;
    for (int i = l; i <= r; ++i) {
        if (SumOfDivisors(i) > i) ++c;
    }
    cout << c;
    return 0;
}

Mình thử nhập input mẫu là 1 50 thì codeblocks lại cho ra kết quả 49 trái với output mẫu. Bạn có thể xem qua giúp mình lỗi ở chỗ nào không. Đoạn code nằm ở phía trên dòng comment “Algorithm begins here” là hoàn toàn đúng đó, mình nghĩ lỗi ở đoạn code dưới mà mình vừa sửa xong.

P/S: Vì liệt kê bằng vòng lặp ko pass 100 điểm của problem nên mình chuyển sang sử dụng sàng nguyên tố để phân tích ra thừa số nguyên tố và dùng CT trên để tính tổng các ước!

#25

lười đọc quá

vậy thì còn gì để sửa đâu ~.~

edit: sum of divisors là có tính cả +i nên dòng if (SumOfDivisors(i) > i) ++c; thêm - i vô là đc

if (SumOfDivisors(i) - i > i) ++c;

…

int minPrime[n + 1];

ngay dòng đầu tiên là tầm bậy rồi, code chạy đc cũng lạ

3 Likes
#26

Hay quá ^^ Mình cũng đang tìm tới dòng đó là bạn phát hiện ra rồi ^^
Thank you so much!

Cái này mình tham khảo thuật toán trên 1 tutorial của vnoi á: http://vnoi.info/wiki/translate/he/Number-Theory-2

Mình cần tính toán trên các phần tử từ 2 đến n, nhưng bỏ qua 0 và 1, nên tổng cộng có n + 1 phần tử. Tức là minPrime[0] và minPrime[1] tồn tại như ko tồn tại vì mình ko sử dụng đến nó!
Và tiếp theo là sử dụng sàng để lọc.

Mà mình submit lên cũng chỉ được 50% số điểm. Bạn thấy có cần cải thiện chỗ nào để thuật toán chạy nhanh hơn ko? (time limit là 0,2s)

#27

trang đó viết tầm bậy chứ còn gì nữa, viết kiểu đó là code C, ko phải code C++

2 Likes
#28

Ừm … Vậy trong trường hợp trên, độ phức tạp của thuật toán (hàm sumofDivisors) có phải là O(logN) nữa ko bạn?

#29

ko vì bạn để cái sàng trong đó… Bưng cái sàng ra ngoài, sàng chỉ chạy 1 lần với N max là đủ

sửa lại cái sàng xài vector cho minPrime

vector<int> minPrime(r + 1, 0); //đã gán 0 cho mọi số
//for (int i = 2; i < (r + 1); ++i) minPrime[i] = 0; ko cần dòng này

muốn nhanh hơn nữa thì tìm cách lập sàng phân đoạn gì ở dưới đó, thay vì tốn r + 1 số thì chỉ cần r - l + 1 thôi

3 Likes
#30

Bưng cái sàng ra ngoài như vầy hả bạn?

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iterator>

using namespace std;

vector<int> Sieve(int n)
{
    // Phan tich n ra thanh cac thua so nguyen to
    vector<int> minPrime(n + 1, 0);
    double sqrt_n = sqrt(n);
    for (int i = 2; i <= (int)sqrt_n; ++i) {
        if (minPrime[i] == 0) {
            for (int j = i*i; j <= n; j += i) {
                if (minPrime[j] == 0)
                    minPrime[j] = i;
            }
        }
    }
    for (int i = 2; i <= n; ++i) {
        if (minPrime[i] == 0)
            minPrime[i] = i;
    }
    vector<int> analyzation; // dung de chua cac thua so nguyen to cua n sau khi phan tich
    while(n != 1) {
        analyzation.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    return analyzation;
}

int SumOfDivisors(int n)
{
    vector<int> analyzation = Sieve(n);
    int sum = 1;
    for (auto it1 = analyzation.begin(); it1 != analyzation.end();) {
        auto it2 = upper_bound(it1, analyzation.end(), *it1);
        int base = distance(it1, it2);
        sum *= ((pow(*it1, base + 1) - 1) / (*it1 - 1));
        it1 = it2;
    }
    return sum;
}

int main()
{
    int l, r, c = 0;
    cin >> l >> r;
    for (int i = l; i <= r; ++i) {
        if ((SumOfDivisors(i) - i) > i) ++c;
    }
    cout << c;
    return 0;
}
#31

sao vẫn còn để trong đây? ~.~ Mà cái này ko phải là sieve mà là minPrime, tạo minPrime trong main, rồi truyền nó vào sumOfDivisors bằng tham chiếu

vector<int> minPrime(int n)
{
    vector<int> minPrime(n + 1, 0);
    int sqrt_n = static_cast<int>(sqrt(n));
    for (int i = 2; i <= sqrt_n; ++i)
        if (!minPrime[i]) //minPrime[i] == 0 nghĩa là i là số nguyên tố
            for (int j = i*i; j <= n; j += i)
                if (!minPrime[j]) //minPrime[j] == 0 nghĩa là j chưa thấy số chia hết nhỏ nhất (nếu != 0 nghĩa là có rồi, khỏi gán)
                    minPrime[j] = i;
    for (int i = 2; i <= n; ++i)
        if (!minPrime[i])
            minPrime[i] = i;  //i là số nguyên tố, minPrime[i] = i
    return minPrime;
}

int SumOfDivisors(int n, const vectorn<int>& minPrime)
{
    vector<int> analyzation; // dung de chua cac thua so nguyen to cua n sau khi phan tich
    while(n != 1)
    {
        analyzation.push_back(minPrime[n]);
        n /= minPrime[n];
    }
    //...
}

int main()
{
    int l, r, c = 0;
    cin >> l >> r;

    auto mp = minPrime(r);

    for (int i = l; i <= r; ++i)
        if ((sumOfDivisors(i, mp) - i) > i) ++c;
    
    cout << c;
}
3 Likes
#32

WOW, pass 100 rồi anh.
Cho em hỏi sao mình cải thiện một vài điểm như trên (bỏ hàm minPrime riêng, tạo vector chứa các thừa số nguyên tố ở hàm khác, dùng tham chiếu) thì thuật toán lại chạy nhanh hơn vậy ạ?

#33

em bỏ cái minPrime trong sumofdiv thì với mỗi i từ L tới R nó tính lại minPrime cho i từ đầu, tốn O(i * log(log(i))), R - L + 1 lần như vậy thì ko biết nó ra bao nhiêu nhưng có lẽ là O(n^2 loglog(n)) với n = R - L + 1

chạy thẳng cái minPrime ở ngoài thì chỉ tốn 1 lần O(n loglog(n)), mỗi lần chạy tính sumofdiv bây giờ chỉ tốn O(log(i)) cho cái vector a còn cái tính sum thì ko biết nhưng cao lắm cũng cỡ O(log(i)) Tổng coogj R - L + 1 lần chỉ tốn O(n logn), cộng lại chỉ còn O(n loglog(n)) + O(n log(n)) = O(n log(n))

truyền tham chiếu để khỏi phải copy lại cái minPrime. Mấy cuộc thi kiểu này nó chơi minPrime là biến toàn cục luôn khỏi mất công truyền tham chiếu… Ở đây mình muốn giới hạn phạm vi minPrime tối đa, chỉ tồn tại trong main() nên phải truyền tham chiếu vô sumofdiv.

với lại lần sau đọc code hiểu nó muốn làm gì cái đã, 1 chức năng = 1 hàm, đừng gộp chung vào. minPrime ra 1 hàm, prime factors ra 1 hàm. Cái đống này:

    vector<int> analyzation;
    while(n != 1)
    {
        analyzation.push_back(minPrime[n]);
        n /= minPrime[n];
    }

đáng lẽ phải tách ra 1 hàm riêng, đừng viết nó ở trong sumofdiv. vì nó có nhiệm vụ riêng. sumofdiv chỉ cần input 1 cái vector primeFactors) rồi output sum of divs

int sumOfDivisors(const vector<int>& primeFactors); //muốn tìm tổng ước nhanh cần các ước nguyên tố
//vector<int> primeFactors(int n); //chậm, O(n^0.5)
vector<int> primeFactors(int n, const vector<int>& minPrime); //nhanh, O(logn), cần phải có 1 mảng minPrime
vector<int> minPrime(int max);

rồi implement từng cái là đc

tl;dr quăng ra ngoài thì nó là O(a) + O(b), bỏ vào trong thì nó thành O(a*b)

3 Likes
#34

Bài này có thể làm được với O(sqrt(R) + (R - L)log(R)).

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?