C/C++程式查詢陣列乘積除以n的餘數？

在這裡，我們將瞭解如何計算陣列乘積除以n後的餘數。陣列和n的值由使用者提供。假設陣列類似於{12, 35, 69, 74, 165, 54}，則乘積將為(12 * 35 * 69 * 74 * 165 * 54) = 19107673200。現在，如果我們想得到除以47後的餘數，它將是14。

正如我們所看到的，這個問題非常簡單。我們可以很容易地將元素相乘，然後使用模運算子得到結果。但主要問題是，當我們計算乘積時，它可能會超過整數或長整型的範圍。因此，它可能會返回一些無效的結果。為了克服這個問題，我們將遵循以下過程。

演算法

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

示例

 即時演示

#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

Arnab Chakraborty

更新於: 2019年7月30日

198 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習