Ruby と crystal で解く AtCoder ABC254 D

# はじめに
AtCoder さん、ありがとうございます。
# D - Together Square
https://atcoder.jp/contests/abc254/tasks/abc254_d

時々出題される、素数系の問題。
# 愚直な例（失敗）
```rb
n = gets.to_i
ans = 0
a = []
k = 1
while k <= n
  a << k * k
  k += 1
end
k = 1
while k <= n
  a.each do |x|
    ans += 1 if x >= k && x % k == 0 && x / k <= n
  end
  k += 1
end
puts ans
```
```rb
while k <= n
  a.each do |x|
```
ここの二重ループが $O(N^2)$ となってしまいますので、**TLE**となります。
# Integer#prime_division
https://docs.ruby-lang.org/ja/latest/method/Integer/i/prime_division.html
## Ruby
```rb
require "prime"

def calc_odd_factor_prod(n)
  ret = 1
  n.prime_division.each do |k, v|
    ret *= k if v.odd?
  end
  ret
end

n = gets.to_i
ans = 0
(1..n).each do |i|
  odd = calc_odd_factor_prod(i)
  j = 1
  while odd * j * j <= n
    ans += 1
    j += 1
  end
end
puts ans
```
素数とくれば`require "prime"`
`Integer#prime_division`で素因数とその指数を算出します。
## crystal
`crystal`には標準で素数関連のクラスが準備されていませんので、自作もしくは公開されているコードを使用する必要があります。

https://github.com/google/ac-library.cr/blob/master/src/Prime.cr

https://github.com/tobyapi/crystalg/blob/master/src/crystalg/number_theory/prime_number.cr

素数関連クラスがある`Ruby`の方が珍しいかも知れませんね。
||Ruby|crystal|
|:--:|--:|--:|
|実行時間(ms)|1630|not started|
# u2dayo さんコード
https://qiita.com/u2dayo/items/e5f0a0f02c530f12b03b#d%E5%95%8F%E9%A1%8Ctogether-square

いつも参考にさせていただいております、@u2dayo さんのコードを~~写経~~移植してみました。
## Ruby
```rb
def calc_odd_factor_prod(n)
  i = 2
  while i * i <= n
    i2 = i * i
    while n % i2 == 0
      n /= i2
    end
    i += 1
  end
  n
end

n = gets.to_i
ans = 0
(1..n).each do |i|
  odd = calc_odd_factor_prod(i)
  (1..n).each do |j|
    break if odd * j * j > n
    ans += 1
  end
end
puts ans
```
残念ですが**TLE**、後`200ms位`改善すればACすると思われます。
本問題は、RubyユーザでのACが少なかったことも頷けます。
## crystal
```cr
def calc_odd_factor_prod(n)
  i = 2
  while i * i <= n
    i2 = i * i
    while n % i2 == 0      
      n //= i2
    end
    i += 1
  end
  n
end

n = read_line.to_i
ans = 0
(1..n).each do |i|
  odd = calc_odd_factor_prod(i)
  (1..n).each do |j|
    break if odd * j * j > n
    ans += 1
  end
end
puts ans
```
計算量が多くても大丈夫。そう、`crystalizer2`ならね。

https://github.com/superrino130/crystal-on-paiza.cloud

||Ruby|crystal|
|:--:|--:|--:|
|実行時間(ms)|TLE|199|
# radiol さんコード
https://qiita.com/radiol/items/b0d5a0fb28485de51f7c#d---together-square

@radiol さんのコードも~~写経~~移植してみました。
## Ruby
```rb
n = gets.to_i
is_sqrt = Array.new(n + 1, false)
(1..).each do |i|
  break if i * i > n
  is_sqrt[i * i] = true
end
factor = Array.new(n + 1){ [] }
(1..n).each do |i|
  i.step(n, i) do |j|
    factor[j] << i
  end
end
cnt = Hash.new(0)
(1..n).each do |i|
  f = 0
  factor[i].reverse.each do |x|
    if is_sqrt[x]
      f = x
      break
    end
  end
  cnt[i / f] += 1
end
ans = 0
cnt.values.each do |v|
  ans += v * v
end
puts ans
```
`factor`配列を用意し、大きい順で検索をしている工夫が光ります。
## crystal
```cr
n = read_line.to_i
is_sqrt = Array.new(n + 1, false)       
(1..).each do |i|
  break if i * i > n
  is_sqrt[i * i] = true
end
factor = Array.new(n + 1){ [] of Int32 }
(1..n).each do |i|
  i.step(to: n, by: i) do |j|
    factor[j] << i
  end
end
cnt = Hash(Int32, Int32).new(0)
(1..n).each do |i|
  f = 0
  factor[i].reverse.each do |x|
    if is_sqrt[x]
      f = x
      break
    end
  end
  cnt[i // f] += 1
end
ans = 0
cnt.values.each do |v|
  ans += v * v
end
puts ans
```
https://crystal-lang.org/api/0.33.0/Number.html#step(*,to=nil,by=1)-instance-method

crystalの`step`メソッド、初めて使用しました。
||Ruby|crystal|
|:--:|--:|--:|
|実行時間(ms)|643|201|
# 気づき（ceil/floor）
`Ruby`の`ceil`や`floor`は**整数**を返しますが、`crystal`の場合**浮動小数点数**を返します。