Discover product of GCDs of all doable row-column pair of given Matrix


Given a matrix of dimension N*M, the duty is to seek out the product of all doable pairs of (i, j) the place i and j are the row quantity and column quantity respectively.

Notice: For the reason that reply could be very giant output the reply modulo 1000000007.

Examples:

Enter: N = 5, M = 6
Output: 5760
Rationalization: The values of GCD of every doable pair

1 1 1 1 1 1
1 2 1 2 1 2
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

Enter: N = 34, M = 46
Output: 397325354

Naive Strategy: To resolve the issue traverse all of the doable pairs of row and column and discover the GCD of them and multiply them with the required reply.

Comply with the steps talked about beneath to implement the thought:

  • Initialize a variable ans = 1 to retailer the product.
  • Iterate from i = 1 to N:
    • For every worth of i traverse from 1 to M.
    • Calculate the GCD of every pair.
    • Multiply this with ans.
  • Return the ultimate worth of ans because the required reply.

Beneath is the implementation of the above method.

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int M = 1e9 + 7;

  

int gridPower(int n, int m)

{

    lengthy lengthy ans = 1;

    for (int i = 1; i <= n; i++) {

        for (int j = 1; j <= m; j++) {

            ans = (ans * __gcd(i, j)) % M;

        }

    }

    return ans;

}

  

int principal()

{

    int N = 5, M = 6;

  

    

    cout << gridPower(N, M) << endl;

    return 0;

}

Time Complexity: O(N*M*log(min(N, M)))
Auxiliary Area: O(1)

Environment friendly Strategy: To resolve the issue comply with the beneath concept:

It may be noticed that for each row, a sample is fashioned until the row quantity and after that, the identical sample 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 instance within the above grid of 4 rows and 6 columns

In row 1, all of the values are 1
In row 2, until index 2 a sample is fashioned and after that very same sample repeats
In row 3, until index 3 a sample is fashioned and after that very same sample repeats

Comparable observations could be made for all different rows.

Therefore for each row, we solely want to seek out the sample as soon as and multiply that sample energy the variety of occasions it happens. This may be carried out utilizing Modular exponentiation methodology. And eventually we have to multiply the remaining sample energy that is the same as Mpercenti for ith row.

Additionally, we are able to take into account the row because the minimal of N and M to scale back time complexity additional.

Beneath is the implementation of the above method:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int M = 1e9 + 7;

  

int fastpower(lengthy lengthy a, int p)

{

    lengthy lengthy res = 1;

    whereas (p > 0) {

        if (p % 2)

            res = (res * a) % M;

        p /= 2;

        a = (a * a) % M;

    }

    return res;

}

  

int gridPower(int n, int m)

{

    lengthy lengthy res = 1;

    for (int i = 1; i <= min(n, m); i++) {

        lengthy lengthy patternPower = 1;

  

        

        

        lengthy lengthy patternOccurence = max(n, m) / i;

  

        

        

        lengthy lengthy stays = max(n, m) % i;

  

        

        

        lengthy lengthy remainsPower = 1;

  

        

        

        for (int j = 1; j <= i; j++) {

            patternPower = (patternPower * __gcd(i, j)) % M;

  

            if (j == stays)

                remainsPower = patternPower;

        }

  

        res = (res

               * fastpower(patternPower, patternOccurence))

              % M;

        res = (res * remainsPower) % M;

    }

    return res;

}

  

int principal()

{

    int N = 5, M = 6;

  

    

    cout << gridPower(N, M) << endl;

    return 0;

}

Time Complexity: min(N, M)*min(N, M)*log(min(N, M))
Auxiliary Area: O(1)

Leave a Reply