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: