結果

問題 No.2266 Fractions (hard)
ユーザー Lisp_Coder
提出日時 2023-04-14 23:01:50
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 822 bytes
コンパイル時間 87 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 20,128 KB
最終ジャッジ日時 2024-10-10 14:04:08
合計ジャッジ時間 14,886 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample TLE * 1 -- * 2
other -- * 35
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:27: warning: assigned but unused variable - primes
Syntax OK

ソースコード

diff # 

require 'prime'

def floor_sum(n, m, a, b)
  ans = 0
  if a >= m
    ans += (n - 1) * n * (a / m) / 2
    a %= m
  end
  if b >= m
    ans += n * (b / m)
    b %= m
  end

  y_max = (a * n + b) / m
  x_max = y_max * m - b
  if y_max == 0
    return ans
  end
  ans += (n - (x_max + a - 1) / a) * y_max
  ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
end

n, k = gets.chomp.split.map(&:to_i)

fractions = []
(1..n).each do |i|
  primes = i.prime_division.map(&:first)
  divisors = []
  (1..i).each do |j|
    if i % j == 0
      divisors.push(j)
    end
  end
  divisors.each do |d|
    if d.gcd(i) == 1
      fractions.push(Rational(d, i))
    end
  end
end

fractions = fractions.sort.uniq
if k > fractions.length
  puts "-1"
else
  puts fractions[k - 1].numerator.to_s + "/" + fractions[k - 1].denominator.to_s
end
0