Задача 715
Модули шестерок

Пусть $f(n)$ будет количеством шестерок $(x_1,x_2,x_3,x_4,x_5,x_6)$, таких что:

  • Все $x_i$ - целые числа, притом $0 \leq x_i < n$
  • $\gcd(x_1^2+x_2^2+x_3^2+x_4^2+x_5^2+x_6^2,\ n^2)=1$

Пусть $\displaystyle G(n)=\displaystyle\sum_{k=1}^n \frac{f(k)}{k^2\varphi(k)}$,
где $\varphi(n)$ - функция Эйлера.

Например, $G(10)=3053$ и $G(10^5) \equiv 157612967 \pmod{1\,000\,000\,007}$.

Найдите $G(10^{12})\bmod 1\,000\,000\,007$.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net