1 / 1

795 : 最大公約数の交代和

正整数 $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$ が与えられている。

$\displaystyle G(N) = \sum_{n=1}^N g(n)$ としよう。 $G(1234) = 2194708$ が与えられている。

$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$ が与えられている。

$\displaystyle G(N) = \sum_{n=1}^N g(n)$ としよう。 $G(1234) = 2194708$ が与えられている。

$G(12345678)$ を求めよ。