Original proposer: rng_58

This problem can be solved clearly with the aid of concept called Gaussian integers.

What are Gaussian integers?

The Gaussian integers are the complex numbers that can be represented as \(a+b\sqrt{-1}\) for integers \(a\) and \(b\). For emphasis, the ordinary integers are sometimes called rational integers. A rational integer is a Gaussian integer. Additions, subtractions, and multiplications of Gaussian integers yield Gaussian integers.

Prime factorization of Gaussian integers

For integers, recall that a prime is an integer \(r\) that cannot be represented as \(n=a\times b\) for two integers \(a\) and \(b\) that are not \(1\) nor \(-1\).

Similarly, for Gaussian integers, a Gaussian prime is defined as a Gaussian integer that cannot be represented as \(n=a\times b\) for two Gaussian integers that are not \(1\), \(-1\), \(\sqrt{-1}\), nor \(-\sqrt{-1}\). For emphasis, ordinary primes are sometimes called rational primes. A rational prime is not necessarily a Gaussian prime.

Just as a rational integer can be factorized into rational primes, a Gaussian integer can also be factorized into Gaussian primes.

Just as the prime factorization of an integer is unique up to \(-1\) factors, as in \(6=2\times 3 = (-2)\times (-3)\), the prime factorization of a Gaussian integer is also unique up to \(\sqrt{-1}\) factors.

(We omit the proof here that Gaussian integers can be uniquely factorized into Gaussian primes because it is very difficult. It is a university-level mathematics; if you are interested, search with terms like “Gaussian integers UFD”.)

Factorization of rational prime into Gaussian primes

A rational prime can be factorized into Gaussian integers and \(\sqrt{-1}\):

• \(2=\sqrt{-1}^3(1+\sqrt{-1})^2\)
• When \(p\) is a rational prime congruent to \(1\) modulo \(4\), there exist integer \(x\) and \(y\) such that \(p=x^2+y^2=(x+y\sqrt{-1})(x-y\sqrt{-1})\), and the two Gaussian integers in the right hand side are Gaussian primes.
• When \(p\) is a rational prime congruent to \(3\) modulo \(4\), \(p\) is a Gaussian prime.

For example, \(5=1^2+2^2=(1+2\sqrt{-1})(1-2\sqrt{-1})\), and the two Gaussian integers in the right hand side are primes.

Obviously, a prime \(p\) congruent to \(1\) modulo \(4\) can be factorized into Gaussian primes by brute-forcing \(x\) in \(O(\sqrt {p} )\) time.

Thus, the Gaussian-prime factorization of all rational primes up to \(P\) can be done in \(O(P^{1.5})\) time. (This can be optimized to \(O(P\log P)\) with an appropriate implementation, but we omit the details here.)

Solving the problem

A point \((x,y)\) is on the circumference of the circle centered at \((a,b)\) with radius \(r\) if and only if \((x-a)^2+(y-b)^2=r^2\). Thus, the problem asks to find the number of integer pairs \((X,Y)\) such that \(\left(X-\frac{A}{C}\right)^2+\left(Y-\frac{B}{C}\right)^2=\frac{N}{C^2}\).

By multiplying both hand sides by \(C^2\) and transposing the terms, we see that it is equivalent to finding the number of integers \((X,Y)\) with \(X^2+Y^2=N\), such that \(X\equiv -A \bmod C\) and \(Y \equiv -B \bmod C\).

Among the rational prime factors of \(N\), let \(p_i\) be those congruent to \(1\), and \(q_i\) congruent to \(3\), modulo \(4\). Let \(p=\pi_p\bar{\pi}_p\) denote the factorization of a prime \(p\) into Gaussian primes.

When \(N\) is factorized within rational integers as \(\prod p^{e_p}\), it is factorized within Gaussian integers as \((1+\sqrt{-1})^{2e_2}\prod\pi_p^{e_p}\bar{\pi}_p^{e_p}\prod q^{e_q}\) (up to \(\sqrt{-1}\) factor).

Problem

Problem 1

First, consider the following problem.

Find the number of integer pairs \((X,Y)\) with \(X^2+Y^2=N\), where \(N\) is given as its prime factorization.

Since \(X^2+Y^2=(X+Y\sqrt{-1})(X-Y\sqrt{-1})\), we regard \(X+Y\sqrt{-1}\) as \(g\) and that the problem asks to find the number of Gaussian integers \(g\) such that \(g\bar{g}=N\). Among the Gaussian integers in the prime factorization of \(N\), the possible complex-conjugate pairs are \(\pi_p\) and \(\bar\pi_p\), \(q\) and \(q\), and \(1+\sqrt{-1}\) and \(1-\sqrt{-1}=\sqrt{-1}^3(1+\sqrt{-1})\)> Therefore, considering which of each of the conjugate pairs is distributed to \(g\) and \(\bar g\), we see that \(g\) can be always represented as

\(\sqrt{-1}^k(1+\sqrt{-1})^{e_2}\prod \pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}\prod q^{e_q/2}.\)

Conversely, any Gaussian integers of this form satisfy \(g\bar g=N\). Therefore the sought count is \(0\) is any \(a_q\) is odd, and \(4\prod(e_p+1)\) otherwise, depending on the decision of \(k\) and \(k_p\).

Problem 2

Now consider the original problem:

Problem: find the number of integers \((X,Y)\) with \(X^2+Y^2=N\), such that \(X\equiv -A \bmod C\) and \(Y \equiv -B \bmod C\).

For simplicity, for a Gaussian integer \(x+y\sqrt{-1}\), let \(x+y\sqrt{-1}\mod C\) denote the integer pair \((x \bmod C,y\bmod C)\).

By the previous problem, it is sufficient to track the distribution of \(\pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}\bmod C\) for each prime \(p\). Since \(\pi_p^{e_p-k_p}\bar{\pi}_p^{k_p}=p^{k_p}\pi_p^{e_p-2k_p}\), it is sufficient to consider \(0\leq k_p \leq e_p/2\) and their complex conjugates. (Beware of the case where \(k_p=e_p/2\).)

The \(C^2\)-vertex graph with edges from \(x+y\sqrt{-1} \bmod C\) to \((x+y\sqrt{-1})\pi_p \bmod C\) suggests that the sequence \(\pi_p^k\bmod C\) on \(k\) has a period of size \(O(C^2)\) for \(k\geq C^2\).

Thus, \(p^{k_p}\pi_p^{e_p-2k_p} \mod C\) for \(0\leq k_p \leq e_p/2\) can be computed in \(\tilde{O}(C^2)\) time by computing the first \(O(C^2)\) terms naively, and using the periodicity for the others.

By naively merging the distributions for the primes \(p\) spending \(O(C^4)\) time, the problem has been solved in \(O(MC^4+P^{1.5})\) time, where \(P = \max P_i\).