นับจำนวนอาร์เรย์ที่สมาชิกติดกันหารกันลงตัวด้วย C++

ได้รับจำนวนเต็มสองจำนวนชื่อว่า one และ another เป้าหมายคือหาจำนวนอาร์เรย์ที่เป็นไปได้ที่ทำให้:

• สมาชิกในอาร์เรย์อยู่ในช่วง 1 ถึง another
• สมาชิกติดกันทุกคู่ ต้องหารกันลงตัว (คือ arr[i] หาร arr[i+1] ลงตัว หรือ arr[i+1] หาร arr[i] ลงตัว)
• ความยาวของอาร์เรย์คือ one

ตัวอย่าง

Input

one = 3, another = 2

Output

Count of arrays in which all adjacent elements are such that one of them divide the another are: 8

Explanation

The arrays will be: [ 1,1,1 ], [ 1,1,2 ], [ 1,2,1 ], [ 1,2,2 ], [ 2,1,1 ], [ 2,1,2 ], [ 2,2,1 ], [ 2,2,2 ]

Input

one = 2, another = 3

Output

Count of arrays in which all adjacent elements are such that one of them divide the another are: 7

Explanation

The arrays will be: [ 1,1 ], [ 2,2 ], [ 3,3 ], [ 1,2 ], [ 1,3 ], [ 2,2 ], [ 3,3 ]

วิธีการที่ใช้ในโปรแกรม

เรารู้ว่าสมาชิกแรกของแต่ละอาร์เรย์สามารถเป็นตัวเลขใดก็ได้ในช่วง [1, another] สมาชิกถัดไปจะต้องเป็นจำนวนเท่าหรือตัวประกอบของสมาชิกก่อนหน้าเสมอ เพื่อให้เงื่อนไขการหารลงตัวเป็นจริง และตัวประกอบหรือจำนวนเท่านั้นต้องน้อยกว่า another เราจะใช้ Dynamic Programming เพื่อเก็บผลการคำนวณ สำหรับนี้ใช้อาร์เรย์ arr[][] โดย arr[1][another] จะเป็น 1 เพราะเป็นอาร์เรย์สมาชิกเดียว สูตรคือ arr[i][j] = arr[i-1][j] + factors of previous element + multiples of previous element (less than another)

• รับจำนวนเต็ม one และ another เป็นอินพุต
• ฟังก์ชัน adjacent_elements(int first, int second) คืนค่าจำนวนอาร์เรย์ที่สมาชิกติดกันหารกันลงตัว
• กำหนดจำนวนนับเริ่มต้นเป็น 0 และอาร์เรย์ arr[size][size]
• กำหนดค่าเริ่มต้นทั้งหมดเป็น 0 ด้วย memset
• สร้างเวกเตอร์สองตัว: vec เก็บตัวประกอบ และ vec_2 เก็บจำนวนเท่า
• วนลูปสองชั้นจาก i=1 ถึง second และ j=2*i ถึง second เพิ่มทีละ i
• เพิ่ม i เข้า vec[j] และ j เข้า vec_2[i] หลังลูป j เสร็จ เพิ่ม i เข้า vec[i] ด้วย
• กำหนด arr[1][i] ด้วยลูป for
• วนลูปอีกครั้ง และวนผ่าน vec และ vec_2 เพื่อบวกตัวประกอบและจำนวนเท่าลง arr[i][j]
• ในที่สุด รวม arr[first][i] ทั้งหมดเข้า count และล้าง vec[i] และ vec_2[i]
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

#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];
    memset(vec, 0, sizeof vec);
    memset(vec_2, 0, sizeof vec_2);
    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 << "Count of arrays in which all adjacent elements are such that one of them divide the another are: " << adjacent_elements(one, another);
    return 0;
}

Output

หากรันโค้ดข้างต้นจะได้ผลลัพธ์ดังนี้:

Count of arrays in which all adjacent elements are such that one of them divide the another are: 4