Being Code Expert: The Confused Monk

The Monk wants to teach all its disciples a lesson about patience since they are always in a hurry to do something crazy. To teach them this, he gives them a list of N numbers, which may or may not be distinct. The students are supposed to solve a simple Mathematical equation based on the array of these N numbers.

1.g(x) - GCD (a[ 0 ], a[ 1 ], a[ 2 ]... a[n-1] )

2.f(x) - (a[ 0 ] * a[ 1 ] * a[ 2 ]... * a[n-1] )

The value of the MonkQuotient is: 109 + 7.

The equation to be solved is: ( f(x)g(x) ) %MonkQuotient

Example:

Input:   n = 2, a = [2,6]
Output: 144

Approach

C++

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007

long long power(long long a, long long b)
{
    if (b == 0)
        return 1;
    if (b % 2 == 0)
        return power((a * a) % MOD, b / 2);
    return (a * power((a * a) % MOD, (b - 1) / 2)) % MOD;
}
long long product(long long a[], long long n)
{
    long long res = 1;
    for (long long i = 0; i < n; i++)
        res = (res * a[i]) % MOD;
    return res;
}
long long gcd(long long a, long long b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
long long FinalCGD(long long a[], long long n)
{
    long long result = a[0];
    for (long long i = 1; i < n; i++)
        result = gcd(a[i], result);
    return result;
}
int main()
{
    long long n = 2;

    long long a[n] = {2, 6};

    long long x = FinalCGD(a, n);
    long long y = product(a, n);

    cout << power(y, x);

    return 0;
}