Problem 795

Alternating GCD Sum

For a positive integer $n$ , the function $g (n)$ is defined as

$g (n) = \sum_{i = 1}^{n} (- 1)^{i} gcd (n, i^{2})$

For example, $g (4) = - gcd (4, 1^{2}) + gcd (4, 2^{2}) - gcd (4, 3^{2}) + gcd (4, 4^{2}) = - 1 + 4 - 1 + 4 = 6$ .

You are also given $g (1234) = 1233$ .

Let $G (N) = \sum_{n = 1}^{N} g (n)$ . You are given $G (1234) = 2194708$ .

Find $G (12345678)$ .

交错最小公约数求和

对于正整数 $n$ ，定义函数 $g (n)$ 为

$g (n) = \sum_{i = 1}^{n} (- 1)^{i} gcd (n, i^{2})$

例如， $g (4) = - gcd (4, 1^{2}) + gcd (4, 2^{2}) - gcd (4, 3^{2}) + gcd (4, 4^{2}) = - 1 + 4 - 1 + 4 = 6$ 。

已知 $g (1234) = 1233$ 。

记 $G (N) = \sum_{n = 1}^{N} g (n)$ 。已知 $G (1234) = 2194708$ 。

求 $G (12345678)$ 。