''' Residue ring modulo m ''' class Zm: m = 7 @staticmethod def setMod(m): n = int(m) if n == 0: raise ValueError("Zero module") if n > 0: Zm.m = n else: Zm.m = (-n) @staticmethod def mod(): return Zm.m def __init__(self, n = 0): self.n = int(n)%Zm.m def __int__(self): return self.n def copy(self): return Zm(self.n) def __add__(self, y): x = (self.n + int(y))%Zm.m return Zm(x) def __radd__(self, y): x = (int(y) + self.n)%Zm.m return Zm(x) def __iadd__(self, y): self.n = (self.n + int(y))%Zm.m return self def __sub__(self, y): x = (self.n - int(y))%Zm.m return Zm(x) def __rsub__(self, y): x = (int(y) - self.n)%Zm.m return Zm(x) def __isub__(self, y): self.n = (self.n - int(y))%Zm.m return self def __mul__(self, y): x = (self.n * int(y))%Zm.m return Zm(x) def __rmul__(self, y): x = (int(y) * self.n)%Zm.m return Zm(x) def __imul__(self, y): self.n = (self.n * int(y))%Zm.m return self def inverse(self): (d, u, v) = extgcd(self.n, Zm.m) if d != 1: raise ZeroDivisionError("division by zero modulo m") return Zm(u) def __truediv__(self, y): k = Zm(y).inverse() return self * k def __rtruediv__(self, y): k = self.inverse() return Zm(y) * k def __itruediv__(self, y): k = Zm(y).inverse() self.n = (self.n * int(k))%Zm.m return self def __pow__(self, n): a = self.copy() k = int(n) if k < 0: k = (-k) a = self.inverse() p = Zm(1) while k > 0: # Invariant: p*a^k == self^n == const if k%2 == 0: k //= 2; a *= a else: k -= 1; p *= a return p def signedResidue(self): m2 = Zm.m//2 if Zm.m%2 != 0: # Symmetric case if self.n <= m2: return self.n else: return self.n - Zm.m else: if self.n < m2: return self.n else: return self.n - Zm.m def __str__(self): return str(self.signedResidue()) def __repr__(self): return str(self) def __eq__(self, y): return (self.n - int(y))%Zm.m == 0 def __ne__(self, y): return not (self == y) def __lt__(self, y): return (self.n < int(y)) def __le__(self, y): return (self.n <= int(y)) def __gt__(self, y): return (self.n > int(y)) def __ge__(self, y): return (self.n >= int(y)) def powmod(a, n, m): # Invariant of loop: b^k * p == a^n b = a; k = n; p = 1 while k > 0: if k%2 == 0: k //= 2; b = (b*b)%m else: k -= 1; p = (p*b)%m if (p < 0): p += m return p def gcd(m, n): a = int(m); b = int(n) while b != 0: r = a%b (a, b) = (b, r) if a > 0: return a else: return (-a) def extgcd(m, n): (a, b) = (int(m), int(n)) (u1, v1) = (1, 0) (u2, v2) = (0, 1) while b != 0: q = a // b r = a % b (u1, u2) = (u2, u1 - q*u2) (v1, v2) = (v2, v1 - q*v2) (a, b) = (b, r) if a > 0: return (a, u1, v1) else: return (-a, -u1, -v1) def invmod(x, m): (d, u, v) = extgcd(x, m) if d != 1: raise ZeroDivisionError("division by zero modulo m") return u