C++ 竞争性编程：简化模 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.

运营商总是处理包装器 class 本身。因此，即使运算符未明确执行模运算，也会在 return 上完成 "boxing" 结果。

然后用它来定义你所有的号码就很简单了:

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

Answer 2

感谢@StoryTeller 和@MSalters，我终于制作了这个可用于解决编码问题的片段-

#define ll long long int
#define MOD 1000000007

template<typename Number, Number m>
class modNum
{
private:
    Number a;
public:
    // overloading '<<'
    friend ostream& operator<<(ostream& os, modNum const & num) {
          return os << num.a;
      }
    modNum(Number a) : a(a % m) {}

    Number get() const { return a; }

    modNum operator+= (modNum b){ a = (a + b.get()) % m; return a; }
    modNum operator*= (modNum b){ a = (a * b.get()) % m; return a; }
    modNum operator/= (modNum b){ a = (a / b.get()) % m; return a; }
    modNum operator-= (modNum b){ a = (a - b.get()) % m; return a; }
    modNum operator + (modNum b){modNum t = (a + b.get()) % m; return t;}
    modNum operator * (modNum b){modNum t = (a * b.get()) % m; return t;}
    modNum operator / (modNum b){modNum t = (a / b.get()) % m; return t;}
    modNum operator - (modNum b){modNum t = (a - b.get()) % m; return t;}

};
typedef modNum<ll, MOD> num_t;
//testing the code-
int int_max = 2147483647;
int sqroot_max = sqrt(int_max);

int main()
{
    num_t sumX(sqroot_max),sumZ(sqroot_max),Y(sqroot_max);
    cout<<(sumX*sumZ + sumX+sumZ)*Y;
    // (((sumX*sumZ) % MOD + (sumX + sumZ) % MOD) % MOD * Y) % MOD;
    return 0;
}

C++ 竞争性编程：简化模 N 下的表达式

C++ competitive programming : Simplifying expressions under modulo N

c++

operator-overloading

operators

modulo