C++

$\color{gold}{— > 蓝桥杯辅导课题解}$

思路：

枚举

$for循环一遍1$~$n - 1, 每次根据题目判断一下这个数是否符合要求$

$(需要注意的是：n可能是个奇数，不能直接 < n / 2： 可以让左边乘2，或者直接将n设为double类型)$

$时间复杂度：O(n)$
$code1:$

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;

    int cnt = 0;
    for (int i = 1; i < n; i ++) 
        if ((i * i) % n * 2 < n)
            cnt ++;
    cout << cnt;
    return 0;
}

$code2:$

#include <bits/stdc++.h>
using namespace std;

int main() {
    double n; cin >> n;

    int cnt = 0;
    for (int i = 1; i < n; i ++) 
        if ((i * i) % (int)n < n / 2)
            cnt ++;
    cout << cnt;
    return 0;
}