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ố

#1

Ta có công thức tính tổng các ước số của một số N = ai x bj x … x ck là: (ai + 1 - 1)/(a - 1) x (bj + 1 - 1)/(b - 1) x … x (ck + 1 - 1)/(c - 1).
Giả sử N = 360 và mình đã có 1 vector lưu lại các thừa số nguyên tố sau khi đã phân tích ra như sau:
2 2 2 3 3 5
Và mình bắt đầu tính tổng các ước của 360 theo công thức trên như sau:

int main()
{ // N = 360 => Sum of divisors = 1170
    vector<int> analyzation(6);
    analyzation[0] = analyzation[1] = analyzation[2] = 2;
    analyzation[3] = analyzation[4] = 3;
    analyzation[5] = 5;
    int sum = 1;
    while(!analyzation.empty()) {
        auto it = find(analyzation.begin(), analyzation.end(), analyzation[0]);
        sum *= ((pow(analyzation[0], *it + 2) - 1) / (analyzation[0] - 1));
        analyzation.erase(analyzation.begin(), analyzation.begin() + *it + 1);
    }
    cout << sum;
    return 0;
}

Nhưng khi compile & run thì Codeblocks bị lỗi, không cho ra kết quả nào hết. IDEone thì báo runtime error: https://ideone.com/LTolca
Mình thực sự ko biết bị lỗi chỗ nào, nhờ mọi người giúp đỡ ạ. Xin cảm ơn!

#2

Có thể là ông pow gây ra.

#3

Có thể bạn đã nhầm :slight_smile: https://en.cppreference.com/w/cpp/algorithm/find

3 Likes
#4

Mình chưa hiểu nhầm ở chỗ nào ạ ?

#5

Mình nghĩ nếu pow() gây ra thì lỗi trong build message của Codeblocks phải nhắc đến chứ đằng này nó ko báo lỗi, vẫn chạy bình thường nhưng chẳng qua màn hình console ko hiện gì hết, đen thui à!

#6

auto it = find(analyzation.begin(), analyzation.end(), analyzation[0]);
bạn có hiểu dòng này đẻ làm gì ko? it nghĩa là cái gì ở đây?

pow(analyzation[0], *it + 2)
*it + 2 là cái gì trong công thức toán trên bạn chỉ ra được ko? Mình thấy nó ghi số mũ là i + 1, j + 1, k + 1 ở đây ra “+ 2” vậy?

analyzation.erase(analyzation.begin(), analyzation.begin() + *it + 1);
analyzation.begin() + *it + 1 nghĩa là gì đây? *it là giá trị của a[x] chứ có phải khoảng cách từ begin tới it đâu?? Viết cái gì đây… Bạn có hiểu it là cái gì chưa đã?

3 Likes
#7

Mình có thử code 1 vài đoạn code thử nghiệm trước thì nếu trong vector có nhiều phần tử trùng giá trị cần tìm val thì std::find sẽ trả về vị trí của val lớn nhất ?
VD: 2 2 2 3 3 5
thì khi dùng std::find với value là 2 sẽ trả về index 2 (phần tử có giá trị 2 nằm ở vị trí 2 - là vị trí lớn nhất)
Khi này, con trỏ it đang giữ vị trí lớn nhất của val cần tìm, mình chỉ cần lấy lũy thừa của val đó với số mũ là vị trí +1 vì vị trí tính từ 0. Trong ví dụ mình nói trên, vị trí lớn nhất của val (2) là 2 nên lấy 22 + 1 là 23.
Xử lý tương tự với val 3 và 5.

Do mình nghĩ *it chính là vị trí của val được tìm thấy, mà chỉ số index luôn tính từ 0 nên để lấy số mũ i + 1 theo công thức, mình cho *it + 2 là số mũ đó ?

Cái này thì mình cũng chưa nắm chắc lắm trước khi code. Thực ra ở dòng lệnh này, mình chỉ muốn xóa đi các phần tử là thừa số nguyên tố mà mình vừa nhân vào thôi. Trong ví dụ trên mình muốn xóa 3 con số 2 chính là 3 phần tử đầu tiên. Nếu chỗ này sai bạn có thể giúp mình sửa lại được ko?

#8

it là “con trỏ” tới phần tử được tìm thấy, *it là giá trị của phần tử đó, ko phải là index của phần tử đó ~.~

2 2 2 3 5
^
it

*it = a[0] = 2
3 Likes
#9

Vậy trong trường hợp trên với find(vector.begin(), vector.end(), 2) thì it sẽ trỏ đến vector[0] hay vector[2] vậy bạn?

#10

vector[0], với vector = 2 2 2 3 5
với vector = 3 3 5 7 (4 phần tử) thì find(vector.begin(), vector.end(), 2) trả về con trỏ tới vector[4] nghĩa là ko có phần tử nào (vector[0]…vector[3] là hợp lệ, iterator tới vector[4] nghĩa là ko có phần tử nào)

bởi vậy đọc vô ngay câu này đã thấy sai rồi

auto it = find(analyzation.begin(), analyzation.end(), analyzation[0]);

//it luôn luôn == analyzation.begin()
3 Likes
#11

Mình chưa hiểu lắm. Mình nghĩ là trong trường hợp trên bạn nói, analyzation[0] là giá trị phần tử đầu tiên của vector là 2, vậy thì std::find cho con trỏ it trỏ đến phần tử có giá trị 2. Nhưng trong ví dụ trên, vector có tới 3 phần tử mang giá trị 2 (là 3 phần tử đầu tiên). Vậy trong TH này, it có trỏ đến analyzation[2] ko hay trỏ đến analyzation[0] vậy bạn?

#12

trỏ tới phần tử đầu tiên nó tìm thấy được. Bạn cho it chạy từ a.begin tới a.end thì nó chạy từ trái sang phải, gặp phần tử nào có giá trị giống đầu tiên thì dừng, tìm hết làm gì cho phí thời gian?

3 Likes
#13

Vậy giờ mình muốn thuật toán trên chạy đúng thì phải làm sao lấy được chỉ số index cao nhất của phần tử có giá trị cần tìm vậy bạn?
Tức là làm sao để lấy ra được index của phần tử mang giá trị 2 cao nhất là 2 để mà nhân vào 23 ấy ?

#14

có nhiều cách lắm:

cách 1: chạy ngược với rbegin và rend. Lưu ý it trả về là it chạy ngược (reverse iterator):

auto rit = find(a.rbegin(), a.rend(), a[0]);

rồi tìm i là số mũ của a[0] thì bạn xài std::distance

auto i = std::distance(rit, a.rend()); //a.rend() có thể hiểu là con trỏ tới a[-1]

cách 2: ko xài reverse iterator, xài std::find_if

auto it = std::find_if(a.begin(), a.end(), [&](int x) { return x != a[0]; }); //tìm con trỏ tới phần tử đầu tiên khác a[0]. [&] là để capture a 
auto i = std::distance(a.begin(), it);

cách 3: vì a đã đc sắp xếp sẵn nên có thể xài binary search, sử dụng std::upper_bound để tìm phần tử đầu tiên lớn hơn a[0]:

auto it = std::upper_bound(a.begin(), a.end(), a[0]);
auto i = std::distance(a.begin(), it);
3 Likes
#15

cũng ko cần xóa 2 2 2 rồi xóa 3 3 v.v… đâu, có thể cho 1 it khác làm a.begin():

bắt đầu với it1 = a.begin()
2  2  2  3  3  5
^
it1

tìm it2
2  2  2  3  3  5
^        ^
it1      it2

tìm xong, gán it1 = it2
2  2  2  3  3  5
         ^
         it1

tìm tiếp it2
2  2  2  3  3  5
         ^     ^
         it1   it2

v.v...
2  2  2  3  3  5
               ^  ^
               it1it2

tới đây it1 == a.end(), dừng
2  2  2  3  3  5
                  ^
                  it1
3 Likes
#16

Ừm, a.rend() trỏ tới index -1 của vector, vậy thì a.rbegin() trỏ đến vị trí a[a.size()] hay sao bạn?

#17

a.rbegin() trỏ tới a[a.size() - 1] :V trỏ tới đúng phần tử cuối cùng, logic giống như a.begin là trỏ tới đúng phần tử đầu tiên. a.end trỏ tới phần tử liền sau phần tử cuối cùng (vô giá trị, ko xài *a.end được) thì a.rend trỏ tới phần tử liên trước phần tử đầu tiên (vô giá trị, ko xài *a.rend được)

bởi vậy xài con trỏ ngược tự dưng phải suy nghĩ ngược mất công lắm, xài cái std::upper_bound mà tìm. Ko thì khi phân tích ra thừa số nguyên tố phân tích thành [(2, 3), (3, 2), (5, 1)] luôn chứ [2, 2, 2, 3, 3, 5] làm gì, thay bằng vector<pair<int,int>> là được

3 Likes
#18

Bạn ơi, mình dùng std::upper_bound().
Theo như bạn nói thì *a.end() ko sài được thì có cách nào để kiểm tra điều đó ko bạn.
Đây là 1 đoạn code mình viết lại nhưng chưa hoàn chỉnh:

int value = analyzation[0];
int sum = 1;
while (...)
{
    auto it = upper_bound(analyzation.begin(), analyzation.end(), value);
    int base = distance(analyzation.begin(), it);
    sum *= ((pow(value, base + 1) - 1) / (value - 1));
    value = *(it + 1);
}

Trong thuật toán trên, mình đã ok ở việc lấy cơ số và số mũ để nhân vào biến sum và cũng ok ở chỗ lấy giá trị của cơ số (value) tiếp theo. Nhưng khi tới value cuối cùng (tức là giá trị 5) thì mình để điều kiện ở vòng while() như thế nào để loop đó dừng lại được bạn?

#19

kiểm tra it != a.end() luôn

for (auto it1 = begin(a); it1 != end(a); ) //end(a) hay a.end() cũng đc
{
    auto it2 = std::upper_bound(it1, end(a), *it1);
    auto i = std::distance(it1, it2);
    //...
    it1 = it2;
}

viết như vầy thì dễ thấy trong thân vòng for, it1 luôn luôn khác end(a) nên luôn luôn lấy *it1 được

*it hay it[0] là value rồi tại sao lại đi gán value = it[1] ~.~

3 Likes
#20

OK mình đã fix lại như sau:

int main()
{ // N = 360 => Sum of divisors = 1170
    vector<int> analyzation(6);
    analyzation[0] = analyzation[1] = analyzation[2] = 2;
    analyzation[3] = analyzation[4] = 3;
    analyzation[5] = 5;
    int value = analyzation[0];
    int sum = 1;
    /*while (true) {
        auto it = upper_bound(analyzation.begin(), analyzation.end(), value);
        int base = distance(analyzation.begin(), it);
        sum *= ((pow(value, base + 1) - 1) / (value - 1));
        if ((it + 1) == analyzation.end()) break;
        value = *(it + 1);
    }*/
    for (auto it1 = analyzation.begin(); it1 != analyzation.end();) {
        auto it2 = upper_bound(it1, analyzation.end(), *it1);
        int base = distance(it1, it2);
        sum *= ((pow(value, base + 1) - 1) / (value - 1));
        it1 = it2;
    }
    cout << sum;
    return 0;
}

nó lại ra kết quả 315 ko như mong đợi :((
Bạn xem giúp mình lỗi ở chỗ nào á?

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