Справедливые числа

У нас с Мишкой на прошедшем соревновании вторая задача прошла претесты, но в зачёт не попала, так как какие-то тесты упали по времени. Сегодня мы с ним её разбирали.

Основные две оптимизации проверки делимости числа:
1. Сначала я собрал все цифры в Set, который ещё дополнительно уменьшил по следующим правилам:

    val set = mutableSetOf<Char>()
    string.forEach { set.add(it) }
    if (set.contains('9')) set.remove('3')
    if (set.contains('8')) set.remove('2' и '4')
    if (set.contains('6')) set.remove('2' и '3')
    if (set.contains('4')) set.remove('2')
    set.remove('1')
    set.remove('0')

2. Потом я оптимизировал проверку делимости BigInteger, используя признаки делимости на 2, 4, 5 и 8. Но эта оптимизация уже не дала сильный прирост, как предыдущая. И всё равно решение задачи не принимали из-за 11-го теста.

Пришлось долго думать над условием, что же я пропустил и понял, что количество проверяемых чисел в одном тесте может быть большим, но туда могут передавать одинаковые или близкие числа. И я добавил кэш Map<Ref>, чтобы не пробегать второй раз для записи в него.

  data class Ref(var value: BigInteger)
  ...
  val dividend = readLine()!!.toBigInteger()
  val applicable = map[dividend] ?: Ref(dividend).also {
    while (true) {
      map[it.value] = it
      if (test(it.value)) break
      it.value = map[++it.value]?.value ?: continue
      break
    }
  }

В результате решение задачи приняли с временем прохождения 1715 мс. Подумав над условием задачи, я понял, что для неё можно не использовать BigInteger, а достаточно использовать Long. Это позволило сократить время исполнения до 1169 мс, а использование памяти - в два раза (с 130000 до 60000 кб)