# 用行或列的最大 GCD 替換每個矩陣元素 > 原文： [https://www.geeksforgeeks.org/replace-matrix-element-maximum-gcd-row-column/](https://www.geeksforgeeks.org/replace-matrix-element-maximum-gcd-row-column/) 給定 **n** 行和 **m** 列的矩陣。 任務是將每個矩陣元素替換為其行或列的最大公因數，以最大者為準。 也就是說，對于每個元素（i，j），請從第 i 行的 GCD 或第 j 行的 GCD 中將其替換，以較大者為準。 **示例**： ``` Input : mat[3][4] = {1, 2, 3, 3, 4, 5, 6, 6 7, 8, 9, 9} Output : 1 1 3 3 1 1 3 3 1 1 3 3 For index (0,2), GCD of row 0 is 1, GCD of row 2 is 3. So replace index (0,2) with 3 (3>1). ``` 這個想法是我們在這里討論的概念 [LCM 的數組](https://www.geeksforgeeks.org/lcm-of-given-array-elements/)，用于查找行和列的 GCD。 使用**暴力**，我們可以遍歷矩陣的元素，找到與該元素對應的行和列的 GCD 并將其替換為兩者中的最大值。 一種有效的**方法**是分別為行和列制作大小為 n 和 m 的兩個數組。 并存儲每一行??和每一列的 GCD。 大小為 n 的數組將包含每一行的 GCD，大小為 m 的數組將包含每一列的 GCD。 并用其對應的行 GCD 或列 GCD 的最大值替換每個元素。 以下是此方法的實現： ## C++ ```cpp // C++ program to replace each each element with // maximum of GCD of row or column. #include<bits/stdc++.h> using namespace std; #define R 3 #define C 4 // returning the greatest common divisor of two number int gcd(int a, int b) { ????if (b == 0) ????????return a; ????return gcd(b, a%b); } // Finding GCD of each row and column and replacing // with each element with maximum of GCD of row or // column. void replacematrix(int mat[R][C], int n, int m) { ????int rgcd[R] = { 0 }, cgcd[C] = { 0 }; ????// Calculating GCD of each row and each column in? ????// O(mn) and store in arrays. ????for (int i = 0; i < n; i++) ????{ ????????for (int j = 0; j < m; j++) ????????{ ????????????rgcd[i] = gcd(rgcd[i], mat[i][j]); ????????????cgcd[j] = gcd(cgcd[j], mat[i][j]); ????????} ????} ????// Replacing matrix element ????for (int i = 0; i < n; i++) ????????for (int j = 0; j < m; j++) ????????????mat[i][j] = max(rgcd[i], cgcd[j]); } // Driven Program int main() { ????int m[R][C] = ????{ ????????1, 2, 3, 3, ????????4, 5, 6, 6, ????????7, 8, 9, 9, ????}; ????replacematrix(m, R, C); ????for (int i = 0; i < R; i++) ????{ ????????for (int j = 0; j < C; j++) ????????????cout << m[i][j] << " "; ????????cout<<endl; ????} ????return 0; } ```