Bounded Quadratic Congruence Problem Variant (for some specific Residue)
Yes.  If $a=1$, the problem is no longer NP-complete; the answer to the problem is always "yes, there is such a positive integer".