许多题目要求进行大量的取模操作。然而,由于除法指令需要较多的 CPU 时钟周期,不必要地对非常量值取模会严重降低程序运行速度,可能导致超过运行时间限制。
#include <iostream>
using namespace std;
int M = 1000000007;
int main()
{
int x = 1;
for (int i = 1; i <= 100000000; i++)
x = 1ll * x * i % M;
cout << x << '\n';
return 0;
}
用该程序计算 ,需要 秒运行时间。而如果将 M
的定义改为
const int M = 1000000007
编译器即可将除法优化成一系列乘法和移位指令,这样就只需要 秒。这只是一个较为简单的测试,在实际中如果取模操作较多,可能产生 倍的时间差距。
只能人工审核所有取模操作。
将题目给定的模数定义为 const
变量。
只要可能,总是应该使用 const
,这样既可以帮助编译器优化代码,也可以防止自己写出其他的低级错误。