class AcLibraryRb::ModInt

ModInt

Attributes

to_i[RW]
val[RW]

Public Class Methods

inv_gcd(a, b) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 47
def inv_gcd(a, b)
  a %= b
  return [b, 0] if a == 0

  s, t = b, a
  m0, m1 = 0, 1
  while t != 0
    u = s / t
    s -= t * u
    m0 -= m1 * u
    s, t = t, s
    m0, m1 = m1, m0
  end
  m0 += b / s if m0 < 0
  [s, m0]
end
mod() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 18
def mod
  $_mod
end
mod=(mod) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 14
def mod=(mod)
  set_mod mod
end
new(val = 0) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 69
def initialize(val = 0)
  @val = val.to_i % $_mod
end
prime?(n) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 28
def prime?(n)
  return false if n <= 1
  return true if n == 2 or n == 7 or n == 61
  return false if (n & 1) == 0

  d = n - 1
  d >>= 1 while (d & 1) == 0
  [2, 7, 61].each do |a|
    t = d
    y = a.pow(t, n)
    while t != n - 1 and y != 1 and y != n - 1
      y = y * y % n
      t <<= 1
    end
    return false if y != n - 1 and (t & 1) == 0
  end
  true
end
raw(val) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 22
def raw(val)
  x = allocate
  x.val = val.to_i
  x
end
set_mod(mod) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 7
def set_mod(mod)
  raise ArgumentError unless mod.is_a? Integer and 1 <= mod

  $_mod = mod
  $_mod_is_prime = ModInt.prime?(mod)
end

Public Instance Methods

*(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 133
def *(other)
  dup.mul! other
end
**(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 112
def **(other)
  $_mod == 1 ? 0 : ModInt.raw(@val.pow(other, $_mod))
end
Also aliased as: pow
+(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 125
def +(other)
  dup.add! other
end
+@() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 104
def +@
  self
end
-(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 129
def -(other)
  dup.sub! other
end
-@() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 108
def -@
  ModInt.raw($_mod - @val)
end
/(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 137
def /(other)
  dup.div! other
end
==(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 141
def ==(other)
  @val == other.to_i
end
add!(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 85
def add!(other)
  @val = (@val + other.to_i) % $_mod
  self
end
coerce(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 121
def coerce(other)
  [ModInt(other), self]
end
dec!() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 79
def dec!
  @val = $_mod if @val == 0
  @val -= 1
  self
end
div!(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 100
def div!(other)
  mul! inv_internal(other.to_i)
end
dup() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 145
def dup
  ModInt.raw(@val)
end
inc!() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 73
def inc!
  @val += 1
  @val = 0 if @val == $_mod
  self
end
inspect() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 157
def inspect
  "#{@val} mod #{$_mod}"
end
inv() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 117
def inv
  ModInt.raw(inv_internal(@val) % $_mod)
end
mul!(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 95
def mul!(other)
  @val = @val * other.to_i % $_mod
  self
end
pow(other)
Alias for: **
sub!(other) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 90
def sub!(other)
  @val = (@val - other.to_i) % $_mod
  self
end
to_int() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 149
def to_int
  @val
end
to_s() click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 153
def to_s
  @val.to_s
end

Private Instance Methods

inv_internal(a) click to toggle source
# File lib_lock/ac-library-rb/modint.rb, line 163
def inv_internal(a)
  if $_mod_is_prime
    raise(RangeError, 'no inverse') if a == 0

    a.pow($_mod - 2, $_mod)
  else
    g, x = ModInt.inv_gcd(a, $_mod)
    g == 1 ? x : raise(RangeError, 'no inverse')
  end
end