HackerRank Number Theory – Hyperrectangle GCD

Challenge: Hyperrectangle GCD

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464744838

Limbaj: python3

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

Cerinta

Let there be a K-dimensional [Hyperrectangle](http://en.wikipedia.org/wiki/Hyperrectangle), where each dimension has a length of n<sub>1</sub>,n<sub>2</sub>,...n<sub>k</sub>.  
Each of the Hyperrectangle's unit cells is addressed at (i,j,k,...) and has a value which is equivalent to GCD(i,j,k,...) where 1 <= i <= n<sub>1</sub> , 1 <= j <= n<sub>2</sub> ....  

The goal is to sum all the GCD(i,j,k,...) cell values and print the result modulo 10^9 + 7. Note that indexing is from 1 to N and not 0 to N-1. 

**Input Format**   
The first line contains an integer T. T testcases follow.  
Each testcase contains 2 lines, the first line being K (K-dimension) and the second line contains K space separated integers indicating the size of each dimension - 
n<sub>1</sub> n<sub>2</sub> n<sub>3</sub> ... n<sub>k</sub>

**Output Format**   
Print the sum of all the hyperrectangle cell's GCD values modulo 10^9 + 7 in each line corresponding to each test case. 

**Constraints**  
1 <= T <= 1000  
2 <= K <= 500  
1 <= n<sub>k</sub> <= 100000

**Sample Input #00**  

	2
    2
    4 4
    2
    3 3
    
**Sample Output #00** 

	24
    12

**Sample Input #01**  

	1
    3
    3 3 3
    
**Sample Output #01**

	30
    
**Explanation #00**   
For the first test case, it's a 4X4 2-dimension Rectangle. The (i,j) address and GCD values of each element at (i,j) will look like  

	1,1 1,2 1,3 1,4              1 1 1 1  
	2,1 2,2 2,3 2,4  => GCD(i,j) 1 2 1 2  
	3,1 3,2 3,3 3,4              1 1 3 1  
	4,1 4,2 4,3 4,4              1 2 1 4  

Sum of these values is 24  

**Explanation #00**  
Similarly for 3X3 GCD (i,j) would look like 

	1,1 1,2 1,3               1 1 1  
	2,1 2,2 2,3  => GCD(i,j)  1 2 1  
	3,1 3,2 3,3               1 1 3  

Sum is 12 

**Explanation #01**   
Here we have a 3-dimensional 3X3X3 Hyperrectangle or a cube. We can write it's GCD (i,j,k) values in 3 layers. 

	1,1,1 1,1,2 1,1,3  |  2,1,1 2,1,2 2,1,3  |  3,1,1 3,1,2 3,1,3  
	1,2,1 1,2,2 1,2,3  |  2,2,1 2,2,2 2,2,3  |  3,2,1 3,2,2 3,2,3  
	1,3,1 1,3,2 1,3,3  |  2,3,1 2,3,2 2,3,3  |  3,3,1 3,3,2 3,3,3  
	GCD (i,j,k)
	1 1 1              |  1 1 1              |  1 1 1  
	1 1 1              |  1 2 1              |  1 1 1  
	1 1 1              |  1 1 1              |  1 1 3  

Total Sum = 30

**Timelimits**
Timelimits for this challenge is given [here](https://www.hackerrank.com/environment)

Cod sursa

from math import ceil

def gcd(a, b):
    if a > b:
        return gcd(b, a)
    while a != 0:
        a, b = b % a, a
    return b

def product(lst):
    prod = 1
    for n in lst:
        prod = (prod * n) % (10 ** 9 + 7)
    return prod
    
# Have a global variable denote the bounds
# Have the function denote how much to divide the bounds by
bounds = None
cache = None
    
def coprime_count(divisor):
    if divisor > bounds[-1] // 2:
        return 1
    if divisor in cache:
        return cache[divisor]
    # bounds are assumed to be sorted
    scaled_bounds = [n // divisor for n in bounds]
    total = product(scaled_bounds)
    cap = scaled_bounds[0]
    # total = sum d from 1 to lowest bound coprime_count(d) (inclusive)
    rest = sum(coprime_count(divisor * d) for d in range(2, cap + 1))
    cache[divisor] = (total - rest) % (10 ** 9 + 7)
    return cache[divisor]
    
t = int(input())
for _ in range(t):
    k = int(input())
    bounds = list(map(int, input().split()))
    bounds.sort()
    cache = dict()
    total = 0
    for i in range(1, bounds[0]+1):
        total = (total + i * coprime_count(i)) % (10 ** 9 + 7)
    print(total)