Skip to content

Latest commit

 

History

History
194 lines (157 loc) · 5.15 KB

整数.md

File metadata and controls

194 lines (157 loc) · 5.15 KB

素数判定 O(log N)

require "prime"
N.prime?

素因数分解 O(√N)

require "prime"
Hash[N.prime_division]

素数列挙 O(N log log N)

require "prime"
primes = Prime.each(N).to_a

N^-1 mod p O(log p)

N.pow(p - 2, p)

N^-1 mod m O(log m)

定数倍は重い

require "openssl"
N.to_bn.mod_inverse(m).to_i

約数列挙 O(√n)

def factors(n, &block)
  e = Enumerator.new do |y|
    k = 1
    while k * k < n
      if n % k == 0
        y << k
        y << n / k
      end
      k += 1
    end
    y << k if k * k == n
  end
  return e unless block_given?
  e.each(&block)
end

約数の総和

約数から求める O(√N)

factors(N).sum

素因数分解から求める <O(√N), O(log N log log N)>

N.prime_division.inject(1) { |prod, (p, e)| prod * (p**(e + 1) - 1) / (p - 1) }

素数テーブル（線形篩） O(N)

class PrimeTable
	def initialize(n)
		@lpf = [nil] * (n + 1)
		@primes = [2]
		(2 .. n).step(2) do |d| @lpf[d] = 2 end
		(3 .. n).step(2) do |d|
			unless @lpf[d]
				@lpf[d] = d
				@primes << d
			end
			@primes.each do |p|
				break if p * d > n or p > @lpf[d]
				@lpf[p * d] = p
			end
		end
	end
	def prime?(n); @lpf[n] == n; end
	def each(&block); @primes.each(&block); end
	def factorize(n); fs = Hash.new(0); while n > 1; fs[f = @lpf[n]] += 1; n /= f; end; fs; end
end

拡張ユークリッドの互除法 O(log N)

def ext_gcd(a, b)
  s, t = b, a % b
  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
  [s, m0]
end

オイラーのφ関数 O(sqrt N)

  • require "prime"
def euler_phi(n)
  return n - 1 if n.prime?
  r = n
  i = 2
  while i * i <= n
    if n % i == 0
      r -= r / i
      n /= i while n % i == 0
    end
    i += 1
  end
  r -= r / n if n > 1
  r
end

N以下の最大の高度合成数 O(log log N) ?

ただし N≦1018

HCN = [1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560, 10080, 15120, 20160, 25200, 27720, 45360, 50400, 55440, 83160, 110880, 166320, 221760, 277200, 332640, 498960, 554400, 665280, 720720, 1081080, 1441440, 2162160, 2882880, 3603600, 4324320, 6486480, 7207200, 8648640, 10810800, 14414400, 17297280, 21621600, 32432400, 36756720, 43243200, 61261200, 73513440, 110270160, 122522400, 147026880, 183783600, 245044800, 294053760, 367567200, 551350800, 698377680, 735134400, 1102701600, 1396755360, 2095133040, 2205403200, 2327925600, 2793510720, 3491888400, 4655851200, 5587021440, 6983776800, 10475665200, 13967553600, 20951330400, 27935107200, 41902660800, 48886437600, 64250746560, 73329656400, 80313433200, 97772875200, 128501493120, 146659312800, 160626866400, 240940299600, 293318625600, 321253732800, 481880599200, 642507465600, 963761198400, 1124388064800, 1606268664000, 1686582097200, 1927522396800, 2248776129600, 3212537328000, 3373164194400, 4497552259200, 6746328388800, 8995104518400, 9316358251200, 13492656777600, 18632716502400, 26985313555200, 27949074753600, 32607253879200, 46581791256000, 48910880818800, 55898149507200, 65214507758400, 93163582512000, 97821761637600, 130429015516800, 195643523275200, 260858031033600, 288807105787200, 391287046550400, 577614211574400, 782574093100800, 866421317361600, 1010824870255200, 1444035528936000, 1516237305382800, 1732842634723200, 2021649740510400, 2888071057872000, 3032474610765600, 4043299481020800, 6064949221531200, 8086598962041600, 10108248702552000, 12129898443062400, 18194847664593600, 20216497405104000, 24259796886124800, 30324746107656000, 36389695329187200, 48519593772249600, 60649492215312000, 72779390658374400, 74801040398884800, 106858629141264000, 112201560598327200, 149602080797769600, 224403121196654400, 299204161595539200, 374005201994424000, 448806242393308800, 673209363589963200, 748010403988848000, 897612484786617600, 1122015605983272000, 1346418727179926400, 1795224969573235200, 2244031211966544000, 2692837454359852800, 3066842656354276800, 4381203794791824000, 4488062423933088000, 6133685312708553600, 8976124847866176000, 9200527969062830400]
def max_hcn(n)
  HCN[HCN.bsearch_index { |x| x > n } - 1]
end

指数タワー mod m

require "prime"

def power_tower(xs, mod)
  mods = [mod]
  (xs.size - 1).times do
    mods << mods[-1].prime_division.inject(1) { |phi, (p, e)| phi * (p - 1) * p**(e - 1) }
  end

  e = 1
  xs.reverse_each do |a|
    m = mods.pop
    e = if e < 10
      b = a**e
      if b < 64
        b
      else
        64 + (b - 64) % m
      end
    elsif a == 0
      0
    else
      a.pow(e, m) + 64 * m
    end
  end

  e % mod
end

N! が p で割り切れる回数

p が素数の場合

def factorial_div_p(n, p)
  e = 0
  e += n /= p while n > 0
  e
end

Floor Sum (Denominator)

$\sum_{i = 1}^{N} \lfloor \frac{N}{i} \rfloor = 2 \sum_{i = 1}^{\lfloor \sqrt N \rfloor} \lfloor \frac{N}{i} \rfloor - {\lfloor \sqrt N \rfloor}^2$

TODO