2021蓝桥杯真题小平方 C语言/C++

问题描述
小蓝发现, 对于一个正整数 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 。

输出格式
输出一个整数, 表示满足条件的数的数量。

样例输入

5

样例输出

2
评测用例规模与约定
对于所有评测用例, 1≤n≤10000 。

运行限制
最大运行时间：1s
最大运行内存: 256M

所需变量
int n;//代表输入的终止条件

int sum = 0;//代表满足此条件的数有多少个

int i;//循环变量

double control;//用于存储n的一半

思路：我们首先要得到n/2将其赋值给control，为什么将control定义为double的目的就是保留这个数一般的比较完整性，因为是小于而不是小于或等于！

double control;
  cin>>n;
  control = n*1.0/2;

得到n/2之后，我们从1开始判断到n-1然后将每个遍历的数都跟control判断一下，如果小于control我们就最终所有总和+1，最终遍历结束我们也就得到了满足条件的所有数！做法如下：

for(i = 1;i<n;i++){
    if((i*i)%n<control){
      sum++;
    }
  }

完整代码如下（编译器是dev，语言是C语言）：

#include <iostream>
using namespace std;
int main()
{
  int n,sum = 0,i;
  double control;
  cin>>n;
  control = n*1.0/2;
  for(i = 1;i<n;i++){
    if((i*i)%n<control){
      sum++;
    }
  }
  cout<<sum<<endl;
  return 0;
}