NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 19 题

阅读程序写结果:

#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

这题就是让你当个‘人工取模机’。拿到x=15，别急着想数论大道理，直接在草稿纸上把0到14一个个算出来：i²除以15余几？等于1就记一笔。循环边界i<x意味着i最大只到14，这点千万盯紧。

最容易翻车的地方有两个：一是循环条件i<x，很多人下意识把15也算进去，结果就多了一个解，答案变成5；二是大数取模，比如11²=121，121÷15商8余1，或者14²=196，196÷15商13余1，心算容易出错，一定要在草稿纸上列竖式或做减法（196-15×13=1），千万别靠脑子硬凑。

程序功能

这段代码的核心逻辑非常直观：读入一个整数x，然后从i=0开始，一直循环到i=x-1（注意是小于x，不是小于等于），在每一次循环里计算i的平方除以x的余数，如果余数恰好是1，就把计数器res加1。最后输出res。

输入给定的数据是15，所以程序实际上是在统计：在0到14这15个数中，有多少个数的平方模15等于1。

逐值列表

为了准确起见，我们老老实实地在草稿纸上把每一个i的情况列出来。这里的关键是取模运算：a % b 就是 a 除以 b 的余数。

满足条件的i有：1, 4, 11, 14，一共 4 个。