Если таблица умножения NxM приведена в порядок, каково число на K позиции?

Question

Если у меня есть таблица умножения 3x4

1 2 3 4
2 4 6 8
3 6 9 12

и все эти числа в порядке:

1 2 2 3 3 4 4 6 6 8 9 12

Какой номер в позиции K?Например, если K = 5, то это число 3.

N и M в диапазоне от 1 до 500 000. K всегда меньше, чем N * M.

Я пробовалиспользовать бинарный поиск как в этом ( Если таблица умножения NxM приведена в порядок, каково число в середине? ), но есть некоторая ошибка, если желаемое значение не находится в середине последовательности.

long findK(long n, long m, long k)
{
    long min = 1;
    long max = n * m;
    long ans = 0;
    long prev_sum = 0;
    while (min <= max) {
      ans = (min + max) / 2;
      long sum = 0;
      for (int i = 1; i <= m; i++)
      {
            sum += std::min(ans / i, n);
      }
      if (prev_sum + 1 == sum) break;
      sum--;


      if (sum < k) min = ans - 1;
      else if (sum > k) max = ans + 1;
      else break;
      prev_sum = sum;
   }


      long sum = 0;
      for (int i = 1; i <= m; i++)
      sum += std::min((ans - 1) / i, n);


    if (sum == k) return ans - 1;
    else return ans;
}

Например, когда N = 1000, М = 1000, К = 876543;ожидаемое значение 546970, но возвращено 546972.

Answer 1

Код третьего метода с этого (https://leetcode.com/articles/kth-smallest-number-in-multiplication-table/#) сайта решить проблему.

bool enough(int x, int m, int n, int k) {
int count = 0;
for (int i = 1; i <= m; i++) {
    count += std::min(x / i, n);
}
return count >= k;

}

int findK(int m, int n, int k) {
int lo = 1, hi = m * n;
while (lo < hi) {
    int mi = lo + (hi - lo) / 2;
    if (!enough(mi, m, n, k)) lo = mi + 1;
    else hi = mi;
}
return lo;

}

Answer 2

Я считаю, что прорыв будет заключаться в подсчете количества факторизаций каждого целого числа до желаемой точки.Для каждого целого числа prod необходимо подсчитать, сколько простых факторизаций i*j существует с i <= m, j <= n.См. Функции делителя .

Вам нужно перебирать prod, пока не достигнете желаемой точки, midpt = N*M / 2.Кумулятивно вычитайте σ0(prod) из midpt, пока не достигнете 0. Обратите внимание, что как только prod проходит min(i, j), вам нужно начинать обрезать счетчик делителей из-за того, что он выходит за границы таблицы умножения.

Этого достаточно, чтобы начать?