P8753 [蓝桥杯 2021 省 AB2] 小平方--2024蓝桥杯冲刺省一

点击跳转例题
本题注意有个小坑，因为题上说小于n的一半，我们的惯性思维就是 n/2，所以要改成 n/2.0
，或者我们分类讨论，判断n是不是偶数，这样就避免C++中除法是向下取整。
 

 n&1类似于n%2。二进制表示 11&01 == 1。      位运算实用总结

 //分类讨论核心代码。
 int x=i*i;
 if(n&1&&x%n<=(n-1)/2)cnt++;
 if(n&1==0&&x%n<n/2)cnt++;

#include <bits/stdc++.h>
#define int long long //(有超时风险)
#define PII pair<int,int>
#define endl '\n'
#define LL __int128
 
using namespace std;
 
const int N=2e5+10,M=1e3+10,mod=998244353,INF=0x3f3f3f3f;
 
int a[N],b[N],c[N],pre[N];
 
signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
 
    int n;cin>>n;
    int  cnt=0;
    for(int i=1;i<n;i++)
    {
        int x=i*i;
        if(x%n<n/2.0)cnt++;
    }
    cout<<cnt<<endl;
 
    return 0;
}