GCD problem | Practice Problems

GCD problem

★★★★★

47 votes

Medium-Hard, Mobius Inversion, Number Theory, Mathematics, Greatest common divisor

Details

Submissions

Discussion

Editorial

Problem

For each set of four integers given $(i,j ,k,l)$ where $1\leq i < j <k <l \leq N$ . You are required to compute the following:

$\displaystyle\sum_{i=1}^{N} \displaystyle\sum_{j=i+1}^{N}\displaystyle\sum_{k=j+1}^{N} \displaystyle\sum_{l=k+1}^{N} gcd(i,j,k,l) ^{4}$

Input format

First line: $T$ that denotes the number of test cases
Next $T$ lines: A integer $N$

Output format

Print the answer for each test case $Mod \,\,\,10^9+7$ in a new line^.

Constraints
$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5$

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

For First Test case N=4 :
(1,2,3,4) : gcd(1,2,3,4)⁴ = 1
Total sum = 1

For Second Test Case N=5 :
(1,2,3,4) : gcd(1,2,3,4)⁴ = 1
(1,2,3,5) : gcd(1,2,3,5)⁴ = 1
(1,2,4,5) : gcd(1,2,4,5)⁴ = 1
(1,3,4,5) : gcd(1,3,4,5)⁴ = 1
(2,3,4,5) : gcd(2,3,4,5)⁴ = 1
Total sum = 1+1+1+1+1 = 5