C++竞技编程: Simplifying expressions under modulo N

Question

codechef 上有很多问题需要对某个数字进行取模运算 like in this one 。我碰巧写了% MOD对于用于例如 - 的每个算术运算符

ans += (((sumX*sumZ) % MOD + (sumX + sumZ) % MOD) % MOD * Y) % MOD;

现在c++中有什么方法可以隐式地做到这一点吗？

尽管this answer说我们不能重载内置类型的算术运算符，但他们仍然有任何方法可以编写 它就像 ans += (sumX*sumZ + (sumX + sumZ)) * Y ？

Answer 1

您可以创建一个小包装器来表示对数量取模的数字。

template<typename Number, Number Width>
class ModuloArithmetic
{
  Number n;
public:
  ModuloArithmetic(Number n) : n(n % Width) {}
  Number get() const { return n; }

  ModuloArithmetic& operator+= (ModuloArithmetic other)
  { n = (n + other.get()) % Width; return *this; }

  // Other modifying operators 
};

template<typename Number, Number Width>
ModuloArithmetic<Number, Width> operator+(
  ModuloArithmetic<Number, Width> lhs,
  ModuloArithmetic<Number, Width> rhs) {
  return lhs.get() + rhs.get();
}

// And so forth for the other arithmetic operations.

运算符始终处理包装类本身。因此，即使运算符没有显式执行模运算，它也会在“装箱”结果时在返回时完成。

然后，根据它定义您的所有号码就很简单了:

using num_t = ModuloArithmetic<int, MOD>;
num_t sumX, sumZ;