Đếm số mảng mà các phần tử liền kề chia hết cho nhau trong C++

Cho hai số nguyên tên là one và another. Mục tiêu là tìm số lượng các mảng có thể có sao cho:

• Các phần tử trong mảng nằm trong phạm vi từ 1 đến another.
• Tất cả các phần tử của mảng sao cho arr[i] chia hết arr[i+1] hoặc arr[i+1] chia hết arr[i+2]... và cứ thế.
• Độ dài của mảng là one.

Ví dụ

Đầu vào

one = 3, another = 2

Đầu ra

Số lượng mảng thỏa mãn điều kiện là: 8

Giải thích

Các mảng sẽ là: [1,1,1], [1,1,2], [1,2,1], [1,2,2], [2,1,1], [2,1,2], [2,2,1], [2,2,2]

Đầu vào

one = 2, another = 3

Đầu ra

Số lượng mảng thỏa mãn điều kiện là: 7

Giải thích

Các mảng sẽ là: [1,1], [2,2], [3,3], [1,2], [1,3], [2,1], [3,1]

Phương pháp sử dụng

Chúng ta biết rằng phần tử đầu tiên của mỗi mảng có thể là bất kỳ số nào trong phạm vi [1, another]. Phần tử tiếp theo sẽ luôn là bội số của phần tử trước hoặc ước số của phần tử trước để điều kiện chia hết được thỏa mãn. Cũng ước số hoặc bội số đó phải nhỏ hơn another. Chúng ta sẽ sử dụng quy hoạch động để lưu trữ các phép tính. Để làm điều này, chúng ta sử dụng mảng arr[][]. arr[1][another] sẽ là 1 vì chúng sẽ là các mảng đơn phần tử. arr[i][j] = arr[i-1][j] + các ước số của phần tử trước + các bội số của phần tử trước (nhỏ hơn another).

• Nhận các số nguyên one và another làm đầu vào.
• Hàm adjacent_elements(int first, int second) trả về số lượng mảng mà tất cả các phần tử liền kề sao cho một trong số chúng chia hết cho cái kia.
• Khởi tạo biến đếm ban đầu là 0 và mảng arr[size][size].
• Khởi tạo tất cả các biến đếm là 0 bằng memset.
• Tạo hai vector: vec để lưu ước số và vec_2 để lưu bội số.
• Duyệt bằng hai vòng lặp for từ i=1 đến i=second và j=2*i đến j=second. Tăng j thêm i.
• Thêm i vào vec[j] và j vào vec_2[i]. Sau vòng lặp j, cũng thêm i vào vec[i].
• Thiết lập arr[1][i] bằng vòng lặp for.
• Duyệt mảng lần nữa và bây giờ duyệt vec và vec_2 và thêm ước số và bội số vào arr[i][j].
• Cuối cùng cộng tất cả arr[first][i] vào biến đếm và xóa vec[i] và vec_2[i].
• Trả về biến đếm làm kết quả.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 
#define size 1000 

int adjacent_elements(int first, int second) {
    int count = 0;
    int arr[size][size];
    memset(arr, 0, sizeof arr);
    vector<int> vec[size], vec_2[size];
    
    for (int i = 1; i <= second; i++) {
        for (int j = 2*i; j <= second; j += i) {
            vec[j].push_back(i);
            vec_2[i].push_back(j);
        }
        vec[i].push_back(i);
    }
    
    for (int i = 1; i <= second; i++) {
        arr[1][i] = 1;
    }
    
    for (int i = 2; i <= first; i++) {
        for (int j = 1; j <= second; j++) {
            arr[i][j] = 0;
            for (auto it: vec[j]) {
                arr[i][j] += arr[i-1][it];
            }
            for (auto it : vec_2[j]) {
                arr[i][j] += arr[i-1][it];
            }
        }
    }
    
    for (int i = 1; i <= second; i++) {
        count = count + arr[first][i];
        vec[i].clear();
        vec_2[i].clear();
    }
    
    return count;
}

int main() {
    int one = 2, another = 2;
    cout << "Số lượng mảng thỏa mãn điều kiện là: " << adjacent_elements(one, another);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số lượng mảng thỏa mãn điều kiện là: 4