自动搬运

查看原文

来自洛谷，原作者为

	kiki_123 (๑╹ヮ╹๑)ﾉ Studying makes me happy

搬运于2025-08-24 22:42:06，当前版本为作者最后更新于2022-12-20 20:48:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{red}\text{题目传送门}$

$\color{red}\text{更好的阅读体验}$

题意

在 $1$ 到 $n-1$ 中，有多少个数平方后除以 $n$ 的余数小于 $n$ 的一半。

分析

从 $1$ 到 $n-1$ 枚举，每次判断 $i\times i \bmod n$ 是否小于 $n/2.0$。

这点有个小坑：一定是 $n/2.0$ 而不是 $n/2$ ，因为 $n/2$ 会自动向下取整，而 $n/2.0$ 得到的是精确值。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n,ans=0;
	cin>>n;
	for(int i=1;i<n;i++)
	{
		if(i*i%n<n/2.0) ans++;
	}
	cout<<ans<<endl;
   	return 0;
}