C++程序求解X^12≡1(mod27)仅输出1，结果异常是什么原因？

问题原因 #

• 误用了浮点数运算函数pow计算整数幂：pow是<cmath>库提供的浮点计算接口，对于大指数的整数运算本身存在精度误差，结果强制转换为int时会截断小数部分，得到的数值和实际整数幂完全不符。
• 整数溢出：32位int类型的最大值仅为2147483647，当i≥4时i的12次方就已经超出了int的取值范围，直接计算会发生溢出，属于C++标准中的未定义行为，后续取模运算的结果自然是错误的。比如i=8时8^12的实际值为68719476736，远大于int的上限，根本无法用int类型正确存储。

修复方案 #

你应该使用模幂运算，每次乘法后都对27取模，既不会出现数值溢出，也不需要调用浮点运算函数，完全规避上述问题。由于指数只有12，直接循环相乘取模即可：

#include <iostream>

int main() {
    for (int i = 0; i <= 2700000; ++i) {
        long long res = 1;
        int base = i % 27; // 利用同余性质提前缩小底数范围，进一步优化性能
        for(int j = 0; j < 12; j++){
            res = res * base % 27;
        }
        if (res == 1) {
            std::cout << i << std::endl;
        }
    }
    std::cout << "Hello, World!" << std::endl;
    return 0;
}

另外利用同余式的性质，x^12 mod 27等价于(x mod 27)^12 mod 27，所以你也可以先预计算出0~26中满足条件的解，后续遍历直接判断i mod27是否属于解集合即可，运行效率会高很多。

内容的提问来源于stack exchange，提问作者Algo