We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Practice
  • Certification
  • Compete
  • Career Fair
  • Hiring developers?
  1. Practice
  2. Mathematics
  3. Number Theory
  4. Hyperrectangle GCD

Hyperrectangle GCD

Problem
Submissions
Leaderboard
Discussions
Editorial

Let there be a K-dimensional Hyperrectangle, where each dimension has a length of n1,n2,...nk.
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 <= n1 , 1 <= j <= n2 ....

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 - n1 n2 n3 ... nk

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 <= nk <= 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

Author

shashank21j

Difficulty

Medium

Max Score

60

Submitted By

187

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature