fork download
  1. require 'prime'
  2.  
  3. # n の因数を列挙した配列を返す
  4. def factors(n)
  5. n.prime_division.inject([1]) do |a, (q, e)|
  6. a.product((0..e).to_a).map {|x, k| x * q ** k}
  7. end
  8. end
  9.  
  10. # Π(1-q) (q は x の素因数)
  11. def f(x)
  12. x.prime_division.inject(1) {|prod, (q, e)| prod * (1 - q)}
  13. end
  14.  
  15. # Σf(x)m(m+1)/2 (x は k の因数, m = floor(n/x))
  16. def F(n, k)
  17. factors(k).inject(0) do |s, x|
  18. m = n / x
  19. s + m * (m + 1) / 2 * f(x)
  20. end
  21. end
  22.  
  23. n, k = gets.split.map(&:to_i)
  24. p F(n, k)
Success #stdin #stdout 0s 28688KB
stdin
9 12
stdout
22