P8753 [Lanqiao Cup 2021 NOI Qualifier AB2] Small Square

Xiaolan found that, for a positive integer $n$ and a positive integer $v$ less than $n$, after squaring $v$ and taking it modulo $n$, the result may be less than half of $n$, or it may be greater than or equal to half of $n$. Ask: among the integers from $1$ to $n-1$, how many numbers have a remainder less than half of $n$ when their squares are divided by $n$. For example, when $n=4$, the remainders of $1^2, 2^2, 3^2$ divided by $4$ are all less than half of $4$. Another example: when $n=5$, the remainders of $1^2$ and $4^2$ divided by $5$ are both $1$, which is less than half of $5$. But the remainders of $2^2$ and $3^2$ divided by $5$ are both $4$, which is greater than or equal to half of $5$.

The input contains one line with an integer $n$.

Output one integer, the number of integers that satisfy the condition.

For all test cases, $1 \leq n \leq 10000$. Lanqiao Cup 2021 Round 2 Provincial Contest, Group A Problem F (Group B Problem G). Translated by ChatGPT 5