โปรแกรม C/C++ หาเศษของการคูณอาร์เรย์ หาร ด้วย n

ที่นี่เราจะดูวิธาคำนวณเศษของการคูณสมาชิกในอาร์เรย์ หลังจากหารด้วย n อาร์เรย์และ n 由ผู้ใช้กำหนด สมมติอาร์เรย์ = {12, 35, 69, 74, 165, 54} การคูณ = 19107673200 หาร 47 เศษ = 14

ปัญหาคือ การคูณอาจเกินขอบเขต integer หรือ long 造成ผลผิดพลาด วิธีแก้: ใช้คุณสมบัติ modulus (a*b) mod n = ((a mod n) * (b mod n)) mod n

อัลกอริทึม

multiplyRemainder(arr, size, n)

begin
    mul := 1
    for i in range 0 to size-1, do
        mul := (mul * (arr[i] mod n)) mod n
    done
    return mul mod n
end

ตัวอย่างโค้ด (C++)

#include <iostream>
using namespace std;

int multiplyRemainder(int arr[], int size, int n) {
    int mul = 1;
    for (int i = 0; i < size; i++) {
        mul = (mul * (arr[i] % n)) % n;
    }
    return mul % n;
}

int main() {
    int arr[6] = {12, 35, 69, 74, 165, 54};
    int size = 6;
    int n = 47;
    cout << "Remainder: " << multiplyRemainder(arr, size, n);
}

ผลลัพธ์

Remainder: 14