Disclaimer: This might enter the realm of mathematical trickery, and not competitive programming itself, but I think it's beautiful enough to mention it here in Codeforces, and maybe invite some competitive programmers to somewhere else where I've recently moved to...

Problem

Given an integer $$$0 \leq N \leq 10^9$$$ as input. Count how many $$$8$$$-tuple $$$x \in \mathbb{Z}^8$$$ are there such that $$$x_1^2 + \dots + x_8^2 = N$$$. The answer may be large, so just output the answer modulo $$$10^9+7$$$.

Ideas

Obvious brute-force takes $$$O(N^8)$$$. Observing that iterating in the square root range is enough reduces it to $$$O(\sqrt{N}^8) = O(N^4)$$$. Trying to divide the problems into two $$$4$$$-tuples with $$$x_1^2+x_2^2+x_3^2+x_4^2 = M$$$ and $$$x_5^2+x_6^2+x_7^2+x_8^2 = N-M$$$ reduces to $$$O(N \cdot \sqrt{N}^4) = O(N^3)$$$. Reformulating the problem into DP/Knapsack gives an $$$O(N^{\frac{3}{2}})$$$ algorithm. Can we do better?

It turns out that in this case, there is an explicit formula! (Yes, mathematical trickery, I know) But the beauty is not in the formula itself, but rather "how does one discover this kind of formula".

I've written a full article on this, which, I feel like it's too long to be rewritten as a Codeforces blog, so I'm putting the link here: My Article.

Note that I've also submitted this article to SoME4, summer 2025, even though I don't think it's a good exposition--it's more like a self-study notes to actually go through and internalize what I've learned.

Please let me know if there is any error or mistake. All feedbacks are appreciated (not just limited to error reporting). I'd be happy to see discussions around this topic!

Also, if I have time, I would maybe set up an actual (experimental -- only for fun) competitive programming task generalizing this (I'm not sure if anyone has prepared a task like this before -- I'm not going to take credits, as it is very classical in the theory and literature, just that it's maybe a bit far from our usual competitive programming style):

(Generalized) Problem

Given integers $$$2 \leq L \leq 1\,000$$$, $$$0 \leq N \leq 10^9$$$, and $$$1 \leq k \leq 100$$$ as input. We guarantee that $$$N$$$ has no prime divisor greater than $$$L$$$. Count the number of integer $$$k$$$-tuples $$$(x_1, \dots, x_k) \in \mathbb{Z}^k$$$ such that $$$\sum_{i=1}^k x_i^2 = N$$$. Since the answer can be large, output modulo $$$10^9+7$$$.