🔙 Back to Top

Wed Dec 1

問題

No.308 素数は通れません - yukicoder

解答

http://yukicoder.me/submissions/61714

Nの制約を一旦忘れて素朴にBFSで解くプログラムを書くと、 小さいNではなんか色々な値が解になって、 それ以降、8かたまに14になる.

パネルは本来 1 から N までしかないが、3N くらいまであるとしてみると、 14は消えて8になった. 巾8のフィールドについて考察してみると、 次のように、全ての合成数に (ほとんどの場合) アクセス可能であることがわかる.

のルートを使って、全ての偶数の合成数にアクセス可能. 奇数の合成数は、全て偶数の合成数の隣にあるので、これもアクセス可能.

実際には (N+1) 以上のパネルは存在しない. これで困るかもしれないのは、 N が奇数で N%8==1 のとき. 隣の偶数 (N+1) から 直接 N に行くことができないので (N-8) から行くしか無い. (N-8) が奇数だと、Nに行けないことになる.

考察はしてないけど、どうやらこのときに解が14になるので間違いない.

# Nが小さい時の解は埋め込み
m={4=>3,6=>5,8=>7,9=>7,10=>7,15=>7,16=>7,22=>7,12=>11,14=>13,20=>19,21=>19,24=>23,25=>23}

require `prime`
n=gets.chomp.to_i
p m[n]?m[n]:(n%8==1&&(n-8).prime?)?14:8 # 大体8、たまに14

これで TLE. WAは出てないので、Prime.prime? だと遅いらしい.

プロコンっぽくないけど、乱択で素数判定する Miller-Rabin 判定を実装してAC.

def powmod(a,k,m)
  return 1 if k == 0
  t = powmod(a, k / 2, m)
  t = t * t % m
  t = t * a % m if k.odd?
  return t
end

def prime?(n)
  return false if n<2
  return true if n<4
  return false if n.even?
  d = n-1
  d >>= 1 while d.even?
  100.times do
    a = rand(n-1) + 1
    y = powmod(a, d, n)
    t = d
    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.even?
  end
  return true
end

として、さきの (n-8).prime? を prime?(n-8) に差し替え.