题目描述
小蓝发现,对于一个正整数 $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 \le n \le 10000$
输入样例:
5
输出样例:
2
样例解释
$1^2 mod 5 < 5 / 2$
$2^2 mod 5 < 5 / 2$
(枚举) $O(n)$
直接枚举判断
C++ 代码
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int res = 0;
for (int i = 1; i <= n - 1; i++) {
if ((i * i) % n < n / 2.0) res++;
}
cout << res << endl;
return 0;
}