3490. 小平方
小蓝发现,对于一个正整数 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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 100000;
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f;
int main()
{
int n;
cin >> n;
double x = n / 2.0;
int res = 0;
for(int i = 1; i < n; i ++ )
{
int a = pow(i, 2);
if(a % n < x)
res ++ ;
}
cout << res << endl;
return 0;
}