[蓝桥杯 2021 省 AB2] 小平方
题目描述
小蓝发现,对于一个正整数 $n$ 和一个小于 $n$ 的正整数 $v$,将 $v$ 平方后对 $n$ 取余可能小于 $n$ 的一半,也可能大于等于 $n$ 的一半。
请问,在 $1$ 到 $n-1$ 中, 有多少个数平方后除以 $n$ 的余数小于 $n$ 的一半。
例如,当 $n=4$ 时,$1,2,3$ 的平方除以 $4$ 的余数都小于 $4$ 的一半。
又如,当 $n=5$ 时, $1$,$4$ 的平方除以 $5$ 的余数都是 $1$,小于 $5$ 的一半。而 $2$,$3$ 的平方除以 $5$ 的余数都是 $4$, 大于等于 $5$ 的一半。
输入输出格式
输入格式
输入一行包含一个整数 $n$ 。
输出格式
输出一个整数,表示满足条件的数的数量。
输入输出样例
输入样例 #1
5
输出样例 #1
2
说明
对于所有评测用例, $1 \leq n \leq 10000$。
蓝桥杯 2021 第二轮省赛 A 组 F 题(B 组 G 题)。