P8753 [蓝桥杯 2021 省 AB2] 小平方 题解

kiki_123 · 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;
}