class AcLibraryRb::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
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