小平方

[蓝桥杯 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

样例输入 #1

5

样例输出 #1

2

提示

对于所有评测用例,1<=n<=10000.

理解

数比较小，可以直接暴力模拟

代码

#include <iostream>
#include<cstdio>
#include <sstream>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
    int n;
    cin>>n;
    int res=0;
    for(int i=1;i<n;i++)
    {
      int num=pow(i,2);
      if(2*(num%n)<n)res++;
    }
    cout<<res<<endl;

    return 0;
}