NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 18 题

阅读程序写结果：

#include <stdio.h>
int main() {
    int x;
    scanf("%d", &x);
    int res = 0;
    for (int i = 0; i < x; ++i) {
        if (i * i % x == 1) {
        	++res;
        }
    }
    printf("%d", res);
    return 0;
}

输入：15

别急着算平方，先盯着那个模运算条件。这题本质是找小于15的正整数里，哪些数的平方除以15余1。把0到14一个个代入看看，符合条件的就计数，最后输出。

最容易栽跟头的就是漏掉那些不在前几个出现的数。比如只盯着1、4、7、8这种小数字算，或者以为平方大了就要手动约分，结果把11和14给漏了。还有种情况是算错模，比如11的平方121，除以15商8余1，有人可能会算成余11或者干脆觉得121太大算不动。记住，循环是从0跑到x-1，也就是0到14，千万别把15算进去，也别漏掉中间跳着的数。

考点与概念

这道题考的是程序阅读，核心在于理解循环结构和分支结构的配合，以及模运算（取余）的规律。题目给了一段C代码，要求输入一个整数x，然后在0到x-1的范围内，统计有多少个i满足 i*i % x == 1 这个条件。

在数学上，i*i % x == 1 意味着 i 是 x 的模逆元（或者叫乘法逆元）。通俗点说，就是找一个数，它的平方除以x余1。在初赛中，这类题通常不需要你懂数论里的欧拉定理或者费马小定理，只需要你会老老实实地模拟循环过程，或者对较小的数心算模运算即可。

命题视角：为什么考这个？

命题人出这题，主要想考察两个点： 1. 对循环边界的敏感度：C语言里 for (int i = 0; i < x; ++i) 是左闭右开区间，即 0, 1, ..., x-1。很多学生习惯性地会算到x，或者漏掉0，这里x=15，范围就是0到14。 2. 模运算的陷阱：当i比较大时，i*i会迅速超过整型范围（虽然15的平方121还在int范围内，但命题人习惯挖坑），或者学生容易把模运算想复杂了。特别是当i是x的倍数时，i*i % x 肯定是0，永远不等于1，所以i=0这种情况直接就可以排除，不需要算。