More than 3 years have passed since last update.

法ｎに基づく整数aの逆数を計算するプログラム

Ruby

Last updated at 2020-02-03Posted at 2020-02-03

invert of integer

def inv(a, n)

  d = n
  x = 0
  s = 1
  while (a != 0)
    q = d / a
    r = d % a
    d = a
    a = r
    t = x - q * s
    x = s
    s = t
  end
  gcd = d  # $\gcd(a, n)$ 

  return ((x + n) % (n / d))
end

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up