问题描述
小蓝发现,对于一个正整数 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≤n≤10000
输入样例:
5
输出样例:
2
思路
这道题同样不难,我们直接枚举出所有情况再判断即可。只是这里要注意的是,在判断是否小于 n 的一半时,不要用除法,因为除法为向下整除,所以我们将除法变为乘法即可。
代码
#include <bits/stdc++.h> using namespace std; int main() { int n, res = 0; cin >> n; for (int i = 1; i < n; i++) { if (i * i % n * 2 < n) res++; } cout << res << endl; return 0; }