NOIP 普及 2018 第一轮 第 22 题：统计模 x 平方等于 1 的整数个数

题目

```cpp
#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

阅读程序写结果:

答案

4

题解

考点定位

本题考「模平方计数」,对应大纲 4.2.1 模拟（难度【2】）。

解题过程

统计 i<x 中 i² mod x == 1 的个数。x=15：i² mod 15 = 1 ⇒ i ≡ ±1, ±4 (mod 15)：i=1,4,11,14 → 4 个。

答案：4。

易错提醒

① i²≡1 (mod x) 的解与 x 的素因子结构相关；② 小 x 直接逐个验。