Chương trình C/C++ tìm dư của tích mảng chia cho n

Ở đây chúng ta sẽ xem cách tính phần dư của phép nhân mảng sau khi chia kết quả cho n. Mảng và giá trị n do người dùng cung cấp. Giả sử mảng như {12, 35, 69, 74, 165, 54} thì phép nhân sẽ là (12 * 35 * 69 * 74 * 165 * 54) = 19107673200. Nếu muốn lấy phần dư sau khi chia cho 47 nó sẽ là 14.

Như chúng ta thấy bài toán này rất đơn giản. Chúng ta có thể dễ dàng nhân các phần tử rồi dùng toán tử modulus để lấy kết quả. Nhưng vấn đề chính là khi tính phép nhân, nó có thể vượt quá phạm vi của int, hoặc long cũng vậy. Vì vậy nó có thể trả về kết quả không hợp lệ. Để khắc phục vấn đề này, chúng ta sẽ làm theo quy trình sau.

Thuật toá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

Ví dụ

#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);
}

Kết quả

Remainder: 14