เราจะมาดูวิธีการคำนวณส่วนที่เหลือของการคูณอาร์เรย์หลังจากหารผลลัพธ์ด้วย n อาร์เรย์และค่าของ n มาจากผู้ใช้ สมมติว่าอาร์เรย์เป็นเหมือน {12, 35, 69, 74, 165, 54} ดังนั้นการคูณจะเป็น (12 * 35 * 69 * 74 * 165 * 54) =19107673200 ทีนี้ถ้าเราต้องการได้เศษที่เหลือหลังจากดำน้ำนี่ โดย 47 มันจะเป็น 14.
อย่างที่เราเห็นปัญหานี้ง่ายมาก เราสามารถคูณองค์ประกอบได้อย่างง่ายดายโดยใช้ตัวดำเนินการโมดูลัส จะได้ผลลัพธ์ แต่ปัญหาหลักคือเมื่อเราคำนวณการคูณ มันอาจเกินช่วงของจำนวนเต็มหรือยาวก็ได้เช่นกัน ดังนั้นจึงอาจส่งคืนผลลัพธ์ที่ไม่ถูกต้อง เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนนี้
อัลกอริทึม
ทวีคูณRemainder(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
ตัวอย่าง
#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
