Clasele 9-10 lecția 5 - 30 oct 2015

From Algopedia
Jump to navigationJump to search

Calcule modulo

template<int MOD>
class Zn {
  long long value; // 0 <= value < MOD

public:
  Zn(int value = 0) {
    this->value = ((value % MOD) + MOD) % MOD;
  }

  Zn operator *(const Zn &other) const { // this * other
    return (this->value * other.value) % MOD;
  }

  Zn operator +(const Zn &other) const { // this + other
    return (this->value + other.value) % MOD;
  }

  Zn operator -() const { // -this
    return (MOD - this->value) % MOD;
  }

  Zn operator -(const Zn &other) const { // this - other
    return (this->value - other.value + MOD) % MOD;
  }

  Zn operator ^(const unsigned int exp) const { // this ^ exp
    if (exp == 0) {
      return Zn(1);
    } else if (exp % 2 == 1) { // b impar
      return (*this) * ((*this) ^ (exp - 1));
    } else { // b par
      Zn ab2 = (*this) ^ (exp / 2);
      return ab2 * ab2;
    }
  }

  Zn operator /(const Zn &other) const { // this / other
    return (*this) * (other ^ (unsigned int)(MOD - 2));
  }

  operator int() const {
    return this->value;
  }
};

Temă

Pentru data viitoare veți avea de rezolvat următoarele 2 probleme: