HackerRank Number Theory – GCD Product

Challenge: GCD Product

Subdomeniu: Number Theory (number-theory)

Scor cont: 150.0 / 150

Submission status: Accepted

Submission score: 1.0

Submission ID: 464736095

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/gcd-product/problem

Cerinta

This time your assignment is really simple.

Calculate GCD(1, 1) * GCD(1, 2) * ... * GCD(1, M) * GCD(2, 1) * GCD(2, 2) * ... * GCD(2, M) * ... * GCD(N, 1) * GCD(N, 2) * ... * GCD(N, M).

where GCD is defined as the [Greatest Common Divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor). 

**Input Format**

The first and only line contains two space separated integers *N* and *M*.

**Output Format**

Output the required product modulo 10<sup>9</sup>+7.

**Constraints**

1 <= *N*, *M* <= 1.5 * 10<sup>7</sup>

**Sample input:**

<pre>4 4</pre>

**Sample output:**

<pre>96</pre>

**Explanation**

For the above testcase, N = 4, M = 4. So, 

GCD(1, 1) * GCD(1, 2) * ...... * GCD(4, 4) = 1 * 1 * 1 * 1 * 1 * 2 * 1 * 2 * 1 * 1 * 3 * 1 * 1 * 2 * 1 * 4 = 96.

Cod sursa

//gcd-product.cpp
//GCD Product
//Weekly Challenges - Week 3
//Author: derekhh

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int MOD = 1000000007;

bool isprime[15000001];
int factor[15000000];

long long ModExp(long long a, long long b, long long n)
{
	long long c = 1, d = a;
	while (b)
	{
		if (b & 1) c = (c*d) % n;
		d = (d*d) % n;
		b >>= 1;
	}
	return c;
}

int main()
{
	int n, m;
	cin >> n >> m;
	memset(isprime, true, sizeof(isprime));
	isprime[0] = isprime[1] = false;
	int nf = 0;
	for (int i = 2; i <= min(n, m); i++)
	{
		if (isprime[i])
		{
			for (int j = i + i; j <= min(n, m); j += i)
				isprime[j] = false;
			factor[nf++] = i;
		}
	}

	long long ans = 1;

	for (int i = 0; i < nf; i++)
	{
		long long tmp = 0, now = factor[i];
		while (n / now && m / now)
		{
			tmp += (n / now) * (m / now);
			now *= factor[i];
		}
		ans = (ans * ModExp(factor[i], tmp, MOD)) % MOD;
	}
	cout << ans << endl;
	return 0;
}