ABC161 F 約数の列挙

2020-W15-1 。月曜日。

ABC161 F を解いた。

約数の列挙についてのメモ。整数 N の約数の列挙は O(√N) 。 1 から √N までの整数 i で試し割りすれば良い。 N を i で割り切れる場合は i と N / i を追加する。

たとえば N = 12 のとき約数は 1, 2, 3, 4, 6, 12 になる。これらは 1 * 12, 2 * 6, 3 * 4 という組になっている。なので 1 のとき 12 / 1 = 12 を……と組で列挙すれば √N までの走査で十分になる。注意するのは N / i を追加すると N / i == i のとき i を二重で列挙してしまう点だ。必要ならソートしても良い。

fn divisors(n: usize) -> Vec<usize> {
  let mut dv = vec![];
  for i in 1.. {
    if i * i > n {
      break;
    }
    if n % i == 0 {
      dv.push(i);
      if n / i != i {
        dv.push(n / i);
      }
    }
  }
  // dv.sort();
  dv
}