Find product of GCDs of all possible row-column pair of given Matrix
Given a matrix of size N*M, the task is to find the product of all possible pairs of (i, j) where i and j are the row number and column number respectively.
Note: Since the answer can be very large output the answer modulo 1000000007.
Examples:
Input: N = 5, M = 6
Output: 5760
Explanation: The values of GCD of each possible pair
1 1 1 1 1 1 1 2 1 2 1 2 1 1 3 1 1 3 1 2 1 4 1 2 1 1 1 1 5 1 The product of grid = 1*1*1*1*1*1*1*2*1*2*1*2*1*1*3*1*1*3*1*2*1*4*1*2*1*1*1*1*5*1 = 5760
Input: N = 34, M = 46
Output: 397325354
Naive Approach: To solve the problem traverse all the possible pairs of row and column and find the GCD of them and multiply them with the required answer.
Follow the steps mentioned below to implement the idea:
- Initialize a variable ans = 1 to store the product.
- Iterate from i = 1 to N:
- For each value of i traverse from 1 to M.
- Calculate the GCD of each pair.
- Multiply this with ans.
- Return the final value of ans as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach: #include <bits/stdc++.h> using namespace std; int M = 1e9 + 7; // Function to calculate the required answer int gridPower( int n, int m) { long long ans = 1; for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { ans = (ans * __gcd(i, j)) % M; } } return ans; } // Driver code int main() { int N = 5, M = 6; // Function call cout << gridPower(N, M) << endl; return 0; } |
Java
// JAVA function to implement above approach import java.util.*; class GFG { // Function to return gcd of a and b public static int gcd( int a, int b) { int result = Math.min(a, b); // Find Minimum of a and b while (result > 0 ) { if (a % result == 0 && b % result == 0 ) { break ; } result--; } return result; // return gcd of a nd b } public static double M = 1e9 + 7 ; // Function to calculate the required answer public static long gridPower( int n, int m) { long ans = 1 ; for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= m; j++) { ans = (ans * gcd(i, j)) % ( long )M; } } return ans; } // Driver Function public static void main(String[] args) { int N = 5 , M = 6 ; // Function call System.out.print(gridPower(N, M)); } } // This code is contributed by sanjoy_62. |
Python3
# Python code to implement the approach: # Function to return gcd of a and b def gcd(a,b): result = min (a, b) # Find Minimum of a and b while (result > 0 ): if ((a % result = = 0 ) and (b % result = = 0 )): break result - = 1 return result # return gcd of a and b # Function to calculate the required answer def gridPower(n, m): ans = 1 for i in range ( 1 ,n + 1 ): for j in range ( 1 ,m + 1 ): ans = (ans * gcd(i, j)) return ans # Driver code N = 5 M = 6 # Function call print (gridPower(N, M)) # This code is contributed by ksam24000 |
C#
using System; public class GFG { // Function to return gcd of a and b public static int gcd( int a, int b) { int result = Math.Min(a, b); // Find Minimum of a and b while (result > 0) { if (a % result == 0 && b % result == 0) { break ; } result--; } return result; // return gcd of a and b } public static double M = 1e9 + 7; // Function to calculate the required answer public static long gridPower( int n, int m) { long ans = 1; for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= m; j++) { ans = (ans * gcd(i, j)) % ( long )M; } } return ans; } static public void Main() { int N = 5, M = 6; // Function call Console.WriteLine(gridPower(N, M)); } } // contributed by akashish__ |
Javascript
<script> // JS code to implement the approach function gcd(a, b) { return b == 0 ? a : gcd(b, a % b); } let mod = 1e9 + 7; // Function to calculate the required answer function gridPower(n, m) { let ans = 1; for (let i = 1; i <= n; i++) { for (let j = 1; j <= m; j++) { ans = (ans * gcd(i, j)) % mod; } } return ans; } // Driver code let N = 5, M = 6; // Function call document.write(gridPower(N, M)); // This code is contributed by Potta Lokesh </script> |
5760
Time Complexity: O(N*M*log(min(N, M)))
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
It can be observed that for every row, a pattern is formed till the row number and after that, the same pattern repeats.
1 1 1 1 1 1 1 2 1 2 1 2 1 1 3 1 1 3 1 2 1 4 1 2 1 1 1 1 5 1 For example in the above grid of 4 rows and 6 columns
In row 1, all the values are 1
In row 2, till index 2 a pattern is formed and after that same pattern repeats
In row 3, till index 3 a pattern is formed and after that same pattern repeatsSimilar observations can be made for all other rows.
Hence for every row, we only need to find the pattern once and multiply that pattern power the number of times it occurs. This can be done using Modular exponentiation method. And finally we need to multiply the remaining pattern power that is equal to M%i for ith row.
Also, we can consider the row as the minimum of N and M to reduce time complexity further.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; int M = 1e9 + 7; // Function to calculate a raised to power // p using Modular exponentiation in // O(log(p)) time int fastpower( long long a, int p) { long long res = 1; while (p > 0) { if (p % 2) res = (res * a) % M; p /= 2; a = (a * a) % M; } return res; } // Function to calculate Grid Power int gridPower( int n, int m) { long long res = 1; for ( int i = 1; i <= min(n, m); i++) { long long patternPower = 1; // Number of times the pattern in // ith row for max(n, m) columns long long patternOccurence = max(n, m) / i; // Part of pattern which will be // left and needs to be multiplied long long remains = max(n, m) % i; // Initialising power of remaining // part of pattern long long remainsPower = 1; // Power of pattern for ith // row calculation for ( int j = 1; j <= i; j++) { patternPower = (patternPower * __gcd(i, j)) % M; if (j == remains) remainsPower = patternPower; } res = (res * fastpower(patternPower, patternOccurence)) % M; res = (res * remainsPower) % M; } return res; } // Driver code int main() { int N = 5, M = 6; // Function call cout << gridPower(N, M) << endl; return 0; } |
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { static int M = ( int )1e9 + 7 ; // Function to calculate a raised to power // p using Modular exponentiation in // O(log(p)) time static long fastpower( long a, long p) { long res = 1 ; while (p > 0 ) { if (p % 2 == 1 ) res = (res * a) % M; p /= 2 ; a = (a * a) % M; } return res; } // Function to calculate Grid Power static long gridPower( int n, int m) { long res = 1 ; for ( int i = 1 ; i <= Math.min(n, m); i++) { long patternPower = 1 ; // Number of times the pattern in // ith row for max(n, m) columns long patternOccurence = Math.max(n, m) / i; // Part of pattern which will be // left and needs to be multiplied long remains = Math.max(n, m) % i; // Initialising power of remaining // part of pattern long remainsPower = 1 ; // Power of pattern for ith // row calculation for ( int j = 1 ; j <= i; j++) { patternPower = (patternPower * __gcd(i, j)) % M; if (j == remains) remainsPower = patternPower; } res = (res * fastpower(patternPower, patternOccurence)) % M; res = (res * remainsPower) % M; } return res; } static int __gcd( int x, int y){ int gcd = 1 ; for ( int i = 1 ; i <= x && i <= y; i++) { if (x % i == 0 && y % i == 0 ) gcd = i; } return gcd; } public static void main (String[] args) { int N = 5 , M = 6 ; // Function call System.out.println(gridPower(N, M)); } } // This code is contributed by aadityaburujwale. |
Python3
# Python code to implement the approach: import math # Function to calculate a raised to power p using # Modular exponentiation in O(log(p)) time def fastpower(a, p): res = 1 while (p > 0 ): if (p % 2 is 1 ): res = (res * a) % M p = math.floor(p / 2 ) a = (a * a) % M return res def gcd(x, y): gcd = 1 for i in range ( 1 , x + 1 and y + 1 ): if (x % i is 0 and y % i is 0 ): gcd = i return gcd # Function to calculate Grid Power def gridPower(n, m): res = 1 for i in range ( 1 , min (n, m) + 1 ): patternPower = 1 # Number of times the pattern in ith row # for max(n, m) columns patternOccurence = math.floor( max (n, m) / i) # Part of pattern which will be left and # needs to be multiplied remains = max (n, m) % i # Initialising power of remaining part of # pattern remainsPower = 1 # Power of pattern for ith row calculation for j in range ( 1 , i + 1 ): patternPower = (patternPower * gcd(i, j)) % M if (j = = remains): remainsPower = patternPower res = (res * fastpower(patternPower, patternOccurence)) % M res = (res * remainsPower) % M return res N = 5 m = 6 M = 1000000000 + 7 # Function call print (gridPower(N, m)) # This code is contributed by lokeshmvs21. |
C#
/*package whatever //do not write package name here */ using System; class GFG { static int M = ( int )1e9 + 7; // Function to calculate a raised to power // p using Modular exponentiation in // O(log(p)) time static long fastpower( long a, long p) { long res = 1; while (p > 0) { if (p % 2==1) res = (res * a) % M; p /= 2; a = (a * a) % M; } return res; } // Function to calculate Grid Power static long gridPower( int n, int m) { long res = 1; for ( int i = 1; i <= Math.Min(n, m); i++) { long patternPower = 1; // Number of times the pattern in // ith row for max(n, m) columns long patternOccurence = Math.Max(n, m) / i; // Part of pattern which will be // left and needs to be multiplied long remains = Math.Max(n, m) % i; // Initialising power of remaining // part of pattern long remainsPower = 1; // Power of pattern for ith // row calculation for ( int j = 1; j <= i; j++) { patternPower = (patternPower * __gcd(i, j)) % M; if (j == remains) remainsPower = patternPower; } res = (res * fastpower(patternPower, patternOccurence)) % M; res = (res * remainsPower) % M; } return res; } static int __gcd( int x, int y){ int gcd = 1; for ( int i = 1; i <= x && i <= y; i++) { if (x % i == 0 && y % i == 0) gcd = i; } return gcd; } public static void Main () { int N = 5, M = 6; // Function call Console.Write(gridPower(N, M)); } } // This code is contributed by Saurabh Jaiswal |
Javascript
let M = 1000000000 + 7; function __gcd(x,y){ let gcd = 1; for (let i = 1; i <= x && i <= y; i++) { if (x % i == 0 && y % i == 0) gcd = i; } return gcd; } // Function to calculate a raised to power // p using Modular exponentiation in // O(log(p)) time function fastpower(a, p) { let res = 1; while (p > 0) { if (p % 2==1) res = (res * a) % M; p = Math.floor(p/2); a = (a * a) % M; } return res; } // Function to calculate Grid Power function gridPower(n, m) { let res = 1; for (let i = 1; i <= Math.min(n, m); i++) { let patternPower = 1; // Number of times the pattern in // ith row for max(n, m) columns let patternOccurence = Math.floor(Math.max(n, m) / i); // Part of pattern which will be // left and needs to be multiplied let remains = (Math.max(n, m) % i); // Initialising power of remaining // part of pattern let remainsPower = 1; // Power of pattern for ith // row calculation for (let j = 1; j <= i; j++) { patternPower = (patternPower * __gcd(i, j)) % M; if (j == remains) remainsPower = patternPower; } res = (res * fastpower(patternPower, patternOccurence)) % M; res = (res * remainsPower) % M; } return res; } let N = 5; let m = 6; // Function call console.log(gridPower(N, m)); // This code is contributed by akashish__ |
5760
Time Complexity: min(N, M)*min(N, M)*log(min(N, M))
Auxiliary Space: O(1)
Contact Us