hikoboshi2

hikoboshi2.rb

#引数nのときのオイラー関数の値を返す
def phi(n)
  result = n
  
  #まず唯一の偶数の素数2で割れるだけ割る
  if n % 2 == 0
    while n % 2 == 0
      n /= 2 #今回は素因数の種類だけが分かればいい(指数は不要なので割るだけ)
    end
    #n(1 - 1/p) = n - n/pなので、 result = result - result / 2 => result -= result / 2;と等価になる
    result -= result / 2
  end
  
  #ここから奇数の素数で素因数分解する
  i = 3
  #n / iの商が iより小さくなったらそれ以上のiでは割れないので終了
  while i <= n / i
    if n % i == 0
      while n % i == 0
        n /= i
      end
      result -= result / i
    end
    i += 2
  end
  #それでもnが残っていれば、それは最大の素因数
  result -= result / n if n > 1
  
  result
end

#1からnまでのオイラー関数の値を合計する
def sum_phi(n)
  (1 .. n).each.inject(0) do |acc, n|
    acc + phi(n)
  end
end


#牛の数を数える
def solve(n)
  #対角線上の半分の値(sum_phi(n-1))の2倍にタブって数えている(1,1)の牛の数1を引いて
  #(1, 0), (0, 1)に置ける牛の数2を足す
  sum_phi(n - 1) * 2 - 1 + 2
end

puts solve(7777777)