Problem #271
GCD Fun
Let f(x_1, x_2, x_3 … x_n) = x_1 * x_2 * ...x_n * (2^{gcd(x_1, x_2, … x_n)}). Let S_n be the sum of f(x_1, x_2, x_3 … x_n) over all sequences (x_1, x_2, x_3 … x_n) where 1 <= x_i <= 10^6. Find S_{31415} modulo 10^9 + 7.
Let f(x_1, x_2, x_3 … x_n) = x_1 * x_2 * ...x_n * (2^{gcd(x_1, x_2, … x_n)}). Let S_n be the sum of f(x_1, x_2, x_3 … x_n) over all sequences (x_1, x_2, x_3 … x_n) where 1 <= x_i <= 10^6. Find S_{31415} modulo 10^9 + 7.