Problem 875

Quadruple Congruence

For a positive integer $n$ we define $q (n)$ to be the number of solutions to:

$a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2} \equiv b_{1}^{2} + b_{2}^{2} + b_{3}^{2} + b_{4}^{2} (\mod n)$

where $0 \leq a_{i}, b_{i} < n$ . For example, $q (4) = 18432$ .

Define $Q (n) = \sum_{i = 1}^{n} q (i)$ . You are given $Q (10) = 18573381$ .

Find $Q (12345678)$ . Give your answer modulo $1001961001$ .

四重同余

对于正整数 $n$ ，定义 $q (n)$ 为如下同余方程的解的数目：
$a_{1}^{2} + a_{2}^{2} + a_{3}^{2} + a_{4}^{2} \equiv b_{1}^{2} + b_{2}^{2} + b_{3}^{2} + b_{4}^{2} (\mod n)$
其中 $0 \leq a_{i}, b_{i} < n$ 。例如， $q (4) = 18432$ 。

定义 $Q (n) = \sum_{i = 1}^{n} q (i)$ 。已知 $Q (10) = 18573381$ 。

求 $Q (12345678)$ ，并对 $1001961001$ 取余作为你的答案。